Ok so I think that everyone agrees that the quest system needs some love.  The quests are way to easy, in general kind of boring and all fall along the same lines.  Here are some thoughts on new types of quests, ways to make them more interesting and how to fix the tech tree a bit. 

New Quests: 

Spawns Monster X: Hey there is now some big ass monster wandering the world that may be more powerful than you anticipated and is capable of destroying some cities, maybe yours, maybe an enemies, but he as something you need.  If he runs into an enemies territory how are you going to get to him?  Declare war, Diplomacy or maybe just wait for him to exit.

Cast Spell X: Hey there is something here that gives a hint as to some sort of spell that it requieres to unlock it.

Chain Quests:  Especially for getting to the master quest but I will address that later.  I think everyone knows how that works though.

Donations:  Lord Whoever wants 30 horses to hand over his sword or something.  Now if you do not have horses you need to find or trade for some, and if you do you need to save some for it.

Antiquest:  Some other guy who thought he was a hero caused some monsters to get pissed and start attacking without the player starting the quest.  It just says hey this is going on.

Questing for Spells/Items/Tech:  I think there should be some techs and spells and items that are found only through questing in every game.  They can either be specific hey this is a quest only spell or random determined at the start of a game.

Making quests better:

The big thing limiting quests right now is player movement.  You don't want it to take 30 turns to complete a quest so the finish has to be near the start which prevents having to enter enemy territory or further explore the world.  The other thing you may want to look at for questing is not allowing armies.  What kind of hero needs an army at his back?

The Master Quest:  I should not be able to research quest level 5 or whatever and then go straight to the master quest.  I think the number and level of quests and locations visited should determine your quest level.  That and I think it should be a quest chain that leads to the master quest. 

Quest Effects:  Make it so quests have an effect on the world.  Maybe like a beast breaks out of a cave and reveals a crystal crag, or some mountain to appear where there was nothing before.  Also have completing quests add to your prestige.  People want to live where heroes are.

Fixing the Quest Tree: 

Reactive items:  Hey some guy wants a wand of fireballs in exchange for a map.  Well I better figure out how to make one.  Oh and now I can make one for my guys.

Hero Only Techs:  Make the items in the questing tree only usable by heroes.  Special armors, weapons and items.

No more researching the next level quests: As said before, quest level based on quests completed.

Quest to reveal the story:  Make it so that some of the quests reveal parts of the history that people otherwise do not see.

Unique Quest Heroes:  Make it so some quests allow you to recruit some better than average heroes.

Please Comment and add your own ideas.