While I have only ever finished one MTW campaign (100%) I have finished many VI campaigns with at least a couple wins for each faction. These got especially challenging after the Beefy Vikings mod came out. Having said that, I still agree that there needs to be some change to make the game more challenging in the later parts. My choice would be to have a coalition of smaller factions join as allies so that if you attack one of them they all attack back. It would just have to be pretty common for smaller factions to form large alliances for it to work. This sort of thing is implemented in Civ4 but it is so rare for factions to form large coalitions that it isn't something you need to routinely worry about.

As for random rebellions, I would hate that. There needs to be certain criteria that one can avoid, just as there was in MTW, so that with care and skill you can have a peaceful empire. You also have to be careful that you don't weaken the stronger AI factions with rebellions because you know that they won't be programmed well enough to avoid them later in the game. This is already a problem in MTW and I would hate to see it made even worse in M2TW.