Why not allow for very powerful characters, but make them very rare. So you won't get one every game, and if a powerful character does appear in your game, there's no guarantee that he won't end up choosing to work for your enemies; but if you do get a fabled hero working for you, then boy are your enemies in for a rough ride
This has a couple of advantages:
Balance isn't so important. As they're not in every game, it doesn't matter that they are overly powerful. Unfair and unbalanced stuff has happened all through human history, so I don't see the problem with unbalancing uber-heroes appearing every now and then.
They won't negate armies. As they won't appear in every game, and not every faction will have access to one. So the bread and butter army building is still important.
It will make games more interesting, increasing the illusion of emergent narrative, and giving Bard (and now Kael?) more opportunities to tell stories with the game.
Kael has done some kinda similar mechanics in FfH2... there's a barbarian hero who appears (every game? early on-ish?) who really isn't very balanced. Any nearby Civs are likely to get crushed. But again, this increases the scope for different games to be different from each other, rather than depending on the same tactics everytime.
Could be implemented as part of a system of catch-up-mechanics. ie, if a hero does appear, then there's a chance he'll have an "hero to the underdog" trait, and go work for a faction that is doing badly. trying to save the day, etc. While this would get annoying if it happened every time (super heroes constantly spawning and stopping you win!), it would be fine if it was only a subtle preference.
Would be a good thing to semi-outsource to the community, creating a roster of fabled heroes and magicians. Give them back stories and interesting traits and preferences. Each faction could have a specific hero that has a very small chance of appearing each game. Each faction could also have a antagonist who has a small chance of appearing and will work for an opposing faction. Some fabled heroes could be strongly tied to a sequence of quests (some equivalent of raising an undead lord, or whatever Elemental's equivalent is! I guess Dragon's kind of fit in here). Some heroes could be tied to other heroes, so if one faction randomly gains access to a special character, then that increases the chance of other characters making themselves available... ie, if some ungodly wraithlord pledges allegiance to one faction, then there's a 33% chance that a paladin will step in to help you defeat it... but not always.... so you'd better get creating a mighty army to stop the wraithlord unleashing hell. (obviously replace wraithlord and paladin for Ele's equivs). Some of them could have access to equivalents of FfH2's "world spells" - spells that you can cast once which have a really large effect on the world. Some heroes could be bound to a single city and unable to move, etc etc etc.
Again, I go back to the balance argument. If they are rare, then they don't have to be balanced. They won't play an important part in your strategy (until you get one) as you only have a small chance of getting one in any game. But if you do get one, then they can be all kinds of powerful, and hence not be a disappointment.
Orthus... You're thinking of Orthus. You're forgetting about the Dragon that usually appears about 60 turns later too.
Me and my cousin used to do RP Games of FFH. We would take the Civs and Leaders he used, and just throw them out. No modding involved here, but we'd ignore that they actually existed, and trade it in for our own Lore and what-not. This is a semi-important preface.
Orthus very commonly killed one of us, forcing us to restart games in order to continue having fun. That became un-fun, very very quickly. Orthus' Axe also got us killed many times, and when one of us had it, it ended games very quickly, for the AI's and ourselves, consequently.
Unbalancing factors, while they do work, are hit or miss events. Either it works, or it doesn't, and you'll never be able to tell which without just playing the game and see. While it adds replayability, and a random element to the game, it takes out the "Strategy" portion of Turn-Based Strategy. Your 'Strategy' either becomes, "Get the unbalancing factor and use said factor to decimate all who stand before me," OR, "KILL THAT SONOVA BITCH! KILL HIM! FIRE FIRE FIRE!" See how that's a problem?
Better in my opinion to make Heroes more scarce, and beef them up. A lot, but not to be army-killing machines. To take an Army, they should need the support of an Army of their own at their back. Spellcasters, being the most rare of them all, should be able to consistently beat Champs to a bloody pulp... Until the Champ gets in their face, and then they should be screwed.
Champions, as the name implies, should be Paragons of Physical Prowess and Skill. Equals in these areas should be few and far between. Barring Administrative-type Heroes, each Realm on a map should have relatively fair potential to get maybe 2 or 3 Champs apiece, to prevent a Champ-Super-Stack being created by anyone. Further, Fallen Champs should only side with Fallen Realms, and vice versa, to add just a little more difficulty to procuring Champions. Lastly, Champs should get abilities to facilitate the idea of them being Much-Better-Than-Average Warriors. Their strength should not come solely from just plain being that much stronger, it should require an Intelligent Strategic and Tactical element, hence the abilities. And only a few, but they should be chosen from a list, based on a trait the Champion has. Traits would be your basic, "I help this kind of puny military unit," type of thing.
That's my 9 Pieces of Eight.
Edit: Oh, and yes, in short, I want kick-ass Champs.