In that case (Tony being fired despite performing well), Larry (the firing knight/king) would be an asshole.
Consider these alternate (admittedly extreme) realities:
A. CEO is an asshole, but manages to bring in $1M/employee in revenue for a company with 500 employees.
B. CEO is a nice guy, but doesn't manage to bring in enough revenue and has to fire 250 of 500 employees.
In reality A, those people who don't think they are paid enough for the abuse, will leave, as they should. In reality B, the choice of who leaves and stays is almost random.
What you say is that firing a reality A CEO is "the right move". The problem is you're extremely likely to get either a reality B CEO, or an asshole with reality B revenue. HP's history since Carly Fiorina would give you a good case study.
So, from almost anyone's perspective, armchair generals excepted, it is NOT the right move.
Edit: oh, and to my original point - in no scenario I can think of would firing someone for abusing their employees or co-workers make one an "asshole".
We don't act like sociopaths and put profits and duties towards boards before people.
But we should not be ignoring the reality, which is that many CEOs are sociopaths (as are many successful politicians). Larry Paige is not, as far as I can tell, a sociopath, but because he does actually have to report to shareholders, he is unlikely to fire someone like Tony Fadell for mistreating his employees as long as he delivers. Fadell didn't, and that's why he's out -- not because of how he treated his employees.
You do propose HP as a case study, but why is it "extremely likely" to lead to that negative outcome?
Also, isn't it possible for a "nice guy" CEO to also bring in high revenue?
I don't think "nice" necessarily equates with "ineffective" in a CEO (for some definitions of "nice").
Competent assholes are far less common than incompetent assholes.
There's a bizarre myth that being an asshole somehow correlates with business competence.
But that doesn't take any account of the large number of asshole CEOs who are crash-and-burn fuck ups.