Are CEOs not at-will employees? I can't sue a company just because they fired me unless it violates certain rights.

The firing itself in an employer-employee sense is fine. But the board has a lot more responsibilities. Firing the CEO for reasons not in the interest of the organisation (e.g. to further some other personal interest) for example is reason for a lawsuit. And the former CEO and boardmember could be to one starting that lawsuit, but so could other parties that suffered damages from this such as shareholders or employees.

I imagine the concerns are more around defamation.