It seems to me that, in the normal course of playing, heroes become extremely powerful while techs, magic, and city builds are still in their infancy.
This is partly the speed with which levels are achieved. It's great that a couple levels or so come quickly, but it seems to me that even weak heroes who get a couple +1 damages in during a battle level up after two out of three battles. (Besides which, leveling seems to be very well designed in this game, but it cheapens the strategic decision if the levels come like a blizzard. You need to feel the tension of the decision, rather than the sense that you can have all these things in a short time.)
More than that, though, the weapons heroes find get way out of hand. When I've hardly dented the second level of techs and I still can't train any sort of army, I'm recovering weapons that are worth thousands and blow away anything I'm likely to encounter.
Also, the lack of consequence for a hero "dying" in a winning battle really unbalances things significantly. I would say that that would be an excellent attribute of an easy level game, but if you want any real tension to battles in normal difficulty games, fallen heroes have to have consequences.
One final reason why heroes level up too quickly: it's kind of like a football passing game when not facing a decent pass rush... I'm not perceiving a credible threat to my towns, so once I eliminate the threats right next to my borders, I can send all my heroes to roam, find more heroes, snap up experience points and weapons, etc. No need to build explorers, at all.