I like the idea of every tile moved by a champion having a very small chance of triggering the generation of an appropriately leveled quest nearby. A faction trait perhaps.[/quote]
There is the wanderlust trait, which lets you buy quest maps in the store. Plus it would be great if each hero in the game could occasionally spawn a quest for you:
Pasted from https://forums.elementalgame.com/405814
Heck, you could use such mechanisms to unlock whole new areas of a map or a unique recruitable unit(s) or even minor faction:
A hero tells you of a hidden pass that leads to a fertile valley and the land of his awesome mounted archers of unerring accuracy. You then gain an opportunity to hire said units, trade for their bows or specially trained mounts, send a child to marry their ruler's offspring and seal them to you or even have it your forces are the tilting point that lets the exiled ruler (your hero NPC) retake his birthright and become a permanent vassal/ally.
These quests could make every phase of the game more exciting. Some could be triggered as you meet certain factions:
"Watch yer back with them Umber scum... they turned on my former liege after signing a bloodtruce." etc...
A lot of litter... um... I mean content, helps keep the sandbox fresh.
edit 2: This is pasted from back in WOM days when there were still minor factions...