So how bad where they before he came
With 9 games to go they were 16th when he took charge, level on points with 18th and only clear of the drop thanks to goal difference. In the 10 games before his arrival they had won 1 game, drawn 4 and lost 5, scoring 7 goals. Under him they won 4 of their last 9 games, scoring 18 goals, including 11 in his first 4 games in charge. In his first full season in charge they finished 7th.
Prior to that Everton had finished 16th (00/01), 13th (99/00) and 14th (98/99) under Walter Smith.
It must also be noted that Everton's financial situation was far worse when he took over than it is now.
He also has a history of developing players into quality Premiership and international players (Osman, Jagielka, Baines, Everton version of Fellaini) and a reputation for helping players find stability and progress (Howard & Pienaar - Spurs' Pienaar was rubbish). The man is not a bad manager at all. He just needs more than five-and-half-months before the knives come out.