I'll be happy if there's a large variety of types of quests that are somewhat contextual. Quest objectives could be the standard (boring by now) collect X, kill Y, but they could also be to build certain things, train units, explore places, research something specific, perform some feat of magic. They could involve heroes doing something on their own, they could be to build up friendly relations with someone, declare war on somebody, defeat somebody - really any type of diplomatic interaction. I'd like to see quest chains, too, in addition to the Master quests (which I'm assuming will be chained, though I could be wrong).
Like I said before, the other important thing to me is that quests are largely contextual. I don't want to be approached by some random civ or being asking me to do some equally random task - at least not often. What I would like to see is something like the Ents of the nearby Great Forest asking me to protect their forest from the effects of the Global Heat spell that was recently cast by somebody, promising to provide me with a suitable reward (in the case of Ents, maybe they'd be willing to provide me with a supply of wood (could be static or over time), maybe they'd be willing to provide me with some special units whose number and/or power depends on the magnitude of their request). Another example is an explorer could offer to tell me the location of ancients ruins as long as I promise to split whatever treasure (could range from resources to magic items) I might find once I defeat the guardians.
Another example of the type of context I want is to avoid what drove me crazy about quests in Sins of a Solar Empire until they somewhat fixed it. The AIs offered me tons of quests that were essentially impossible to complete. Sometimes towards the beginning of a game I was asked to destroy X structures within 10 minutes, and the entire nation didn't even have that many structures to destroy! And sometimes I was asked to destroy ships or structures of an empire that I couldn't effectively reached. That should be avoided at all costs.
Also, quest rewards should be anything including resources (both one-time and over time), units, items, better relations or other diplomatic rewards, technology, magic, part of the map explored, settlements, resource nodes, and I'm sure there are other good rewards. And both the type of reward and the magnitude need to be reflected by the type and difficulty of the quest.