I think the basic idea here is very sound, although it will be tough to implement, I think. I would like to see the following:
1) Keep the current system of random quests being offered to the player.
2) Have some quests offered to the player based on the buildings the player builds (this has been mentioned frequently, ie: I build a tavern, I can now visit that Tavern and get quests or engage in other actions) and the overall gameplay situation (ie: some quests generated by wars, treaties, etc). I think this will be fairly each to implement.
3) Have some special dynamic quests such as the Dragon or whatever.This would be amazingly cool, but possibly hard to implement.
4) Allow the player to call for heroes to go questing, similar to Majesty. These heroes would then independently go questing, use the player's cities and buildings for resupply, etc.