Really great ideas, ArcElement2002! Champions with enchanted swords is always fun, but this idea would really help improve the enjoyability of running your cities and other, more mundane activities. But personally, I don't think we should limit it to just the sovereign. I would propose that any city being governed by a hero is eligible for uncovering "civic quests" (though the best quests go only to the sovereign). In fact, I see your idea as a great way to level up those heroes who don't go out and fight, but merely manage cities.
Reading your ideas made me think about what kind of quests we'd be looking at. I came up with a couple ideas. Were these the kind of quests you were considering?
"Milord, a legal dispute has arisen between a banker and a war hero over an investment gone bad. They have appealed to your benevolent wisdom to resolve the case. [You must decide which citizen wins the case. Choosing the banker temporarily increases accrued funds to the city, but recruitment time is temporarily halved, and vice versa for the war hero. Or, for a cost, you can resolve the case by paying for the bad investment yourself, which earns you the benefit of one of the citizens without the penalty of the other.]"
"Your highness, Athanasius the Scholar has emerged after disappearing during the Cataclysm. He says that he is willing to teach his greatest secrets to the people that prove themselves worthy. The first faction to construct four universities in four different cities will earn Athanasius' loyalty, and his secrets. [This is a global quest, so every "governor sovereign" gains access to it at the same time. You have to race against the other factions to win this quest. Winning means that all schools/universities/etc. in the four cities gain extra knowledge production capabilities.]"
"Governor, our archeologists have recently uncovered an ancient artifact buried underneath the foundations of the city. Our most learned mages claim it is a mystical tome that will grant eternal blessings to the city. But the mages warn that using the tome may have a cost... [After the quest initiates, the tome must be transported to the capital. The carrier of the tome is safe while he is in the city, but once he steps out, he will be attacked every turn by spawned monsters. Successfully making it to the capital earns your city a free enchantment.]"
"My lord, I trust you remember the recent negotiations we held with the empire of Resoln. The trade agreement we established has greatly benefitted this mighty city and its most productive citizens. However, murmurings within the empire of Resoln are dwindling their faith in our wares. Your advisors feel that a trip through Resoln lands would improve their faith in our product. [The quest is triggered by a recently-signed trade agreement pact and a governor in a city benefitting from the trade. The quest requires the governor to visit four trade-partner cities and return to his own city, earning his city an extra trade route and a temporary boost to trade income. However, the quest always triggers for one governor from each nation, so you're racing against your trade partner to finish the quest first.]"
"Your majesty, our war with Altar has taken an interesting turn for the better. An Altarian who sympathizes with our cause has defected to us, and lies within the city walls. He promises to reveal information about Altar's battle plans to us, if we provide him safe transport back to our capital. Unfortunately, the informant was wounded as he fled to our lands, and so the travel will be difficult. [Quest triggered in a city bordering a nation with whom you are at war. The enemy will be notified of the defection, and presumably put a high priority on keeping the defector from reaching the capital. Successfully getting the informant to the capital will temporarily let you see the enemy nation's Line of Sight. Alternatively, you can decline the mission as a matter of honor, which will temporarily cut the closest enemy city's recruitment production in half]."
