Help me, I really, really would like to see almost all of the changes mentioned above and can't decide.
I'm a bit greedy so I'll go with AI (both campaign and battlefield), unit balance and bribing.

I was a HoMM enthusiast for many years (all games before HoMM4) and thoroughly agree with Simon's suggestions. Building an uber stack and using that stack intelligently and aggressively would go a long way to making the AI much more of a threat.

Well, let's see if the coming patch for AI is any good... and if it isn't, it's time for yet more rant... mwahahahaha