I know there are plans to have wandering monsters and hero and that it may be possible for them (in some cases) to join your nation, but it may also be fun to develop the idea of wandering wizards.  These could be modeled after those in LOTR-each with its own distinct personality.  Some just wander around the map and are interested in only obscure things (wild life, the course of streams, forests).  Others may have an interest in more worldly affairs and my try to intervene in battles.  Others may build a house or fortress in a corner of the map and mostly stay there-either as a hermit, or helping to protect a certain forest for region, or to build up a fortress and gather up their own army.

So they would act like lesser-channelers.  They could be considered good, evil, or neutral (or chaotic I suppose).  Their may be events that could change the alignment or behavior of these wizards as well.  You could approach them to ask a favor (ranging from a blessing, an artifact, a map where other crystals could be found, or help in a battle).  Depending on their interests and inclinations, they could blast you off the map before you finished your sentence, passage through their land, demand a tribute of some sort, complete a quest first, or demand help in a battle.  Also, not all wizards may be trusted - the item he gives you could be cursed, the map could be faulty, he could be leading your army into a trap (fighting a much larger army than imformed you about, ect).  Some of these less nomatic wizards could also protect a region of the map (like a forest of desert) setting up protective borders.  If you find yourself next to one of these "protected regions" you might want to tiptoe around the borders until you have a better feel for your neighbor or try to use resources that are found within.  Tresspassers (depending on their alignment, magical resistance, and the whim of the wizard) have a chance of being cursed, turned into zombies,  having magic items taken,  attached by magical beings (trees, whirlwinds, i don't know) or you may gain an audience with the resident wizard.  Depending on how that meeting goes this could set your nations relationship with this wizard.  But, like any wizard, it would probably never be wize to fully trust him.

I realize this may be hard to code for but maybe not since there is already going to be heros, monsters, a good AI, and quests.  Like dragons, they should be rare (there was only 5 in LOTR) and very formidable but they should also be defeatable if you put enough effort into it.  This could go a long way towards making the game world more alive and mysterious. 

Anyway, something to talk about while we wait for the beta.