I definitely think rewards are important. Maybe some rinky-dink quests have mundane rewards, but I think rewards should stretch across all the game mechanics. Rewards should also be signficant for signficant quests, balance is not as important as the coolness factor of rewards (difficulty level can be the balancing force, not altering the rewards, but just in giving the ai so many advantages anyway). There is nothing lamer than doing something significant in a game for a trivial reward.
1. The quest results in a suped up hero character for hire. (Possibly he was imprisoned in a dungeon, or bound to a demon that has to be slain to release him).
2. The quest results in a book which gives a skill to the sovereign (ex. one of the powerful bonuses that can be chosen at startup.
3. The quest results in an advanced spell for the sovereign.
4. The quest results in an artifact that has kingdom-wide bonuses (ex. increased production, morale, wealth)
5. You resolve a quest originating from another kingdom, thus there are kingdom-wide penalties for that kingdom because you successfully completed it. For instance, certain towns can have issues and if another kingdom solves them, that causes problems for the home kingdom (potentially flipping the city).
6. Solving a quest has an unexpected effect, like one of the random events in Gal Civ 2, possibly good and possibly bad.
7. A special unit becomes availble to the sovereign (like the dragon or something else).
8. A neutral town joins your kingdom.
9. A fountain imbues one hero character with several levels worth of attribute enhancements.
10. Solving a menacing creature invasion results in gifts and positive diplomatic effects from other kingdoms.