It was probably coming to be honest. They spent a lot of money over the summer and haven't really performed this season. Bruce has never really managed to stay at a club for too long and build a proper team (you could argue that there is a reason for that). Always started okay and then gone down from there really. Although you'd have to say that the departures of key players like Henderson, Bent, Gyan, Welbeck (albeit he was a loan) haven't helped.
As for replacements, I think they'd do well to get Moyes out of Everton but I reckon someone like O'Neill or Hughes would do a decent job for them. Much like us you could say, they have a decent squad but just need the right manager to get the best from them.