I concur that the "Uber-Hero Strategy" is the best thing around. I mainly play the campaigns and it gets nasty. I think the big thing is that heroes are almost always going to be better than your L4 creatures once you get them to level ten or so. In the campaign this is especially huge since you don't have to pay for them and they come with you. Anyway, I think a good answer would be to make getting higher level units much faster. -1 turn to build on everything, 2 turn upgrades, and 1 turn installs for L2s and L3s (2 turn installs for L4s). That will really cut into your super heroes because if I can afford to sacrifice L4 units I'll be sending stacks of Karaghs after a hero very quickly and no big if they don't do it...the next one will be right behind them. (Gets off his soapbox)
As for my gameplay strategy it is as follows:
1.) Explore quickly emphasizing towers and cheap resources(unprotected mines/builder's guilds/mana nodes). Best to use flyers if you have them to start (always keep flyers with you in the campaign) or your fastest availible unit that isn't your hero (Azrac elephant is great b/c it can capture other player's towers).
2.) While exploring send your "hero stack" (mult. heroes if availible or your leader and a calvary unit or two) out to collect treasures/xp. During this time it is okay for your hero to capture some cities and wait for them to migrate since you'll need the gold and your explorers should be doing their thing.
3.) Once your explorer finds the heart of your opponents land, send them into his undefended heartlands to snipe resources as you powerrush your spelled up hero stack (waterwalking/liquid form/free movement/windwalking is a must have) straigt at the enemy leader....one less...one less...one less ***** ya gotta worry about! I did this in the final scenario of the cult campaign and had defeated Gabirel and Joseph by turn 11. The Undead were already sniped on turn 9 when a couple air galleys went to town on Inioch. I was so bored with slaughtering the independents that I finally just did the freemove cheat to move my hero stack up to Julia and seal the deal.
In many of the middle campaign scenarios there is an enemy leader very close to your starting location. If you have flyers you can have a massive portion of the map explored by the time you reach turn 5. That is normally when I would knock out the nearest leader. Of course, I am normally playing against the AI who sends its forces out en masse at the start and leaves its hero holding the bag at home. Those neutral wandering stacks will hurt you for a bit, but more experience for your hero!
Something else I've noticed about the AI is that if you move a threat up into it's heartland it will normally switch modes as it were. This is another reason I strongly recommend flyers. I've flown a wyvern rider right past an enemy leader's town on the other side of the map and found that the leader started to mass his forces in his home city like it is so prone to do in the endgame. This helps a bit if you are encountering his scouts in your lands, and might well ensure that you won't have to worry much about his forces for the rest of the game. Although this only happened noticably once.
Sorry for the length of this post.
Feyd Rautha, Stormlord Extraordinaire