Carrying out a task for a reward is nice, but what really makes quests (or any strategic decision) interesting is scarce resources and decisions that involve trade-offs. Rather than a player seeing a quests pop up and thinking:

"Oh good, I can get some extra troops/money/status/resource X/etc, I just need to click on the right spots on the screen an extra thirty times", setting up quests as strategic dilemma gets users thinking:

"Oh god, the chances for fantastic riches, but I'd need to risk so much and you never know with these quests what unexpected opportunities and risks will pop up mid-way through, do I have the time and resource base to attempt this just now?"

Some possibilities off the top of my head are:

(Prisoner's Dilemma style) 

A powerful warlock has appeared in your kingdom. He claims he draws his magic from a different source than you do, but has no wish to become entangled in your kingdom's affairs. He has merely come to retrieve the [Orb of Zot, etc]. He offers you (a good amount of money, scaled to player's current economy) if you help him.

Do you (these should be enacted by the players decision while on the quest):

big cooperate) Agree and complete the quest faithfully, but risk him not paying you, or this being some sort of ruse to lure you away so he can take over your kingdom

small negotiate) Agree, but insist on getting the [orb] for yourself (and risk him retracting the offer and going to your competitors)

small betrayal) Agree, but then take the [orb] at the last minute after you're both exhausted from fighting the [dragon] (and maybe steal his money too)

big betrayal) Agree and then once you have his trust, capture the warlock and perform experiments on him to determine the source of his power

Each option should have a (real, i.e. randomly determined over a probability function computed from the player's stats/resources/actions)  chance of both earning rewards and penalties, depending on how the player plays it, how strong they are relative to the warlock, what precautions they take (i.e. leaving a small army outside the cave that he ventures into with the warlock) and so on

(Public Good Game style)

A genie is granting minor wishes (one per person) to the first X people who visit him. Most have already been spent before your troops could isolate him from the peasant populace. Massive crowds have gathered and daily the guards catch people trying to sneak through. Do you:

a) Make your wish right away before anyone else can sneak past your guards and get to him, then pay others (or threaten them) to go make your other wishes for you (but risk their betraying you)

Have a fair competition (or lottery) to determine whose wishes will be granted

c) Allow the most needy to have their wishes granted

d) Allow the richest (or those with the most power to repay you) to have their wishes granted (i.e. sell the wishes)

e) Save the wishes for a rainy day (but take a large risk on their being stolen, in the meantime)

When you wish, do you: ask for something that benefits the people (but gives you less strategic advantage in the game), ask for something that benefits you or ask for something that benefits the genie in the hope that he'll reward you for it (but risk wasting a wish).

(Negative Indirect Reciprocity style) - All players get this quest at the same time

Temporary portals have begun opening at random between the kingdoms, your sages have determined that one end can be tethered but the other will fluctuate wildly. By tethering one end of a portal in your castle, you can have troops constantly monitoring its destination, and if it ever opens in your opponent's castle you could do some serious damage or steal his resources. Of course, your opponent also has a tethered portal and could do the same. A summit is held, wise scribes from each kingdom attend and come back with a resolution. Only harm can come of this technology and if it begins, eventually harm will come to everyone, thus they have signed a treaty agreeing that no-one should use the portals in this way.

Later, each player can randomly receive the message:

Your guards inform you that a portal has opened to [random opponent]'s castle - do you

a) obey the treaty, do nothing

send x troops to do as much damage as they can, though they will ultimately be sacrificed when the portal shifts

c) send a small brigade of thieves to steal as much as they can before the portal closes

if they chose b or c, there's a chance that they can be identified and all the other players informed that they have broken the treaty.

Wealthy Veteran <name> has found an infant <harpy/half-siren> and wishes to raise her as his daughter.

1. Please do so (greatly increases prestige, could anger citizens [somehow], could lead to either a "missing men" event or an "angry harpies" event) ++ liberal //chaotic

2. We will not be raising such monstrosities! (kills harpy, veteran leaves) + totalitarian //neutral

3. We will return such a creature to her natural habitat (quest to the harpy lair, diplomatic event with Harpy nation/Harpy tribe, chance for battle so bring soldiers) + liberal //good

4. Harpies! In our lands! Exterminate the foul beasts! (quest to harpy lair, many, many battles. veteran leaves) ++totalitarian //lawful

5. Imprison the creature for Study and entertainment! (prestige bonus, research bonus, definitely will lead to "angry harpy event" possibly multiple times [battle with harpies]) ++ totalitarian //chaotic

will only become a "quest" if either option 3 or 4 is selected from the events selection.

(if you've noticed, I think that, at least with events, having a tri-axis decision: Moral Alignment(good/lawful/evil/chaotic), Constitutional Alignment(liberal/totalitarian), and direct effect (increased prestige/decreased gold). Increases the role-play and spices up the decision making process. Perhaps the same can be said for quests as well) however, even if its only a dual-axis decision, I think it will be superior to only differentiating via direct effect.

as simply a spur of the moment idea for such roles, Totalitarian can give bonus to over-all production (especially military), while Liberal can give bonus to prestige, (especially) trade routes, possibly research. Moral values would effect Diplomatic relations, and how various characters and creatures would interact with you. Although this is merely simple idea. Tri-Axial decision making in any form would be interesting if it is congruent with the rest of the game. (if it adds to much complexity then it would simply be taking away ... but I would hope this would be all basic form for the Diplomacy tech tree) what I mean is that I would expect tech tree to increase bonuses related to Morality and level of Authoritarianism, as the next step of the Alignment techs from GalCiv.

After playing a lot of Dragon Age, I would like to see a long quest line where depending on what you do, different things will happen.  Example:

1. King Ozymandius requests help for his kingdom.
- Train 10 troops and Send them over
- Send over 100 food
- Send 500 Gold
- Send Instructors to Teach them

If you choose to send over troops, you get +10 to relations, and a new quests to do a joint attack on a dungeon defended by a mighty dragon.

If you send 100 food, you would get +5 relations, but a side effect, is that the hungry smith over there ends up starting a new quest for you to supply him with metal to build the best weapons he can.

If you send 500 gold, you get +15 to relations.  This opens a quest line where you get involved in a pyramid scheme with him.

If you send instructors, you get no change in relations, but it allows you to open a new quest in researching the history of his empire, you find a clue to a treasure map that may bring great riches.

I think with most of these quests ... remove the word (dragon) and insert the word (troll, giant, or centaur).

In this way, only the really, really high-end quests (like on par or even greater than the Titan's Sword / Demon quest) will actually have to deal with a dragon, since on a giant map there are maybe 5 dragons? Unless these other, random dragons are much younger and less legendary.

As for the kill 10 of creature X it can be done if it's done sensibly. Rather then have some lunitic who because the cities sewers are overrun with rats, posted a bounty of 30gp for killing exactly 10 rats once... Have someone with more common sense offer a bounty that will have you paid 3gp for every rats tail you bring him (And don't make rats tails random drops, you kill rat you can cut off its tail, it shouldn't have a 1 in 5 chance of appearing in the rats backpack). So this way a player can hunt rats as long (Or short) as they can tolerate to earn an equivilent reward for their time. To make it more interesting make the rats spawn rat variable. The more rats the player kills the lower their spawn rate in that region. The longer they go without killing a rat the higher the spawn rate in that region climbs. As an additional reward if the player collects on 1000 rats (actualy a random number they are unaware of) you could have the NPC reward them with say... a ring of rat slaying for their explary service. Insert Dragon, Troll, Spider, Channelers, Tree zombie, etc in place of rat at random... Or based on their spawn rates in a given area.

The prospect of good and evil quest options and quest that affect everyone and have them compete has been proposed. I think it can be done in a more interesting fashion then just... A rumour of an artifact of ultimate doom has been circulating, find it before everyone else, or be the first to slay the dragon guarding the holy mountain for and artifact or kill the player holding and hold it yourself to be rewarded with a boost to food production while ever you hold it... Examples: 

Player X gets offered the following quest: Collect numerous tomes thoughout the land and build a great library to boost research production. Upon accepting or completing this quest other players will be given quest offers, such as: Player Y: Obtain one or more of certain tomes and keep them out of player X's possesion for a certian number of turns or more interestingly an oppertunist has heard player X is collecting tomes and is willing to act as a middle man between you and he to sell any of the tomes you can gather before he does to him. THe longer you hold the tomes the higher they will sell for, but hold them to long and player X might loose interest. Player Z: Player X is building collecteing certian tomes to build a library in his glory, destroy them before he can. Or, find and replace and replace a certain number of the tomes with fake copies sabotaging the project by filling the library with false information that will benifit you more then he. Of once the player X completes the quest give player y a quest to capture the library for himself and player Z a quest to burn the library or steal the contents.

You could also have similar quests which would effect the diplomatic landscape forcing alliances and wars out of need. A deamon asks you to commit genocide agaisnt player X completing a 1000 year old ritual that will open the gates of hell (Or equivelent) and summon a horde of deamons to ravager the land. Of course if you do this they will leave you alone. MEanwhile player Y gets a quest to stop you by destryoing you or protecting player X, Player Z gets a quest open the gates to heaven (or equivilent), Player Q gets a quest to sever the links between heaven and hell making the opening of such gates impossible. After the gate is open quests go out like take contorl of the gate for yourself, destroy the gate, ressurect player X... It would beintersting if being the victem if destroyed player X becomes the army of deamons until revived. Point is theres alot more you can do with it then, everyone races for an identicle goal.

Another great thing I'd like to see is treasure hunt quests. Theres a couple of ways you could do this, like the hereos of might and magic method of having an obscured treasure map and having more and more parts of the map revealed as you collect more pieces of the map. Or you could have a very small map with a minimal number of landmarks to go by. Additionaly and perhaps more itnerestingly you could have a randomly generated set of instructions in poem form that directs you to the treasure. Basicaly have the game pick where the treasure will be, look at the surrounding landmarks, form a path to the treasure using the landmarks then have each line of the peom give a random description for each type on landmark. E.g. Start where once proud structures no longer stand (ruins), Follow the sun (West) a number of paces equal to the figers on one hand (5), From where the earth rises to meet the sky (Mountains), travel rightward (North relative to last direction) till the this you do spy (No fixed distance, just keep going till you reacht he enxt landmark described), A place where earthern giants to stand (A different random descrption for hills/mountains), Now travel the way of the path of day (A different random description for west), travel paces equal to a boxes sides (6), Find a place were forever sleeping creatures lie (A graveyard) etc. etc.

Lets not forget the quest to help the baker bake some loaves of bread. Every 1 in 10 times the quest comes up have him bake bread of the gods. The bread must be made from the eggs of dragon the milk of a unicorn and the dough must be kneeded by falling of ogres.

There are quite a lot of good examples here.  I do not repeat them here.   Hopefully, what I said below has not been mentioned... 

Its been mentioned a couple of times but I'd like to see a set of quests that have a direct impact on diplomacy.  I kind of see the quests system as being part of a larger espionage system.  What I'm actually envisioning is something along the lines of the actions that probe teams carried out in Alpha Centauri.  So I can see offering quests as the soveriegn like "foment rebellion in X Kingdom" and this leads to someone founding a death cult in that kingdom or something like that.  Being an old D&D player the idea of having espionage and counter-espionage quests really appeals to me.  And depending on my Adventuring tech level, the ability of other kingdoms to trace the funding of said quest back to me would change as well as the types of quests I can offer.  Also, if there's a morality system, the outcomes of my quests would change.  So, if I had the "rebellion" quest on offer, and I were good, the Adventurers might preach against the corruption of X kingdom and the freedoms that my people have.  If I were evil, they would start the death cult or maybe engage in random acts of barbarism to show X Kingdom can't protect them or something.

These quests could also have a direct impact on warfare.  Revealing the map, assassinating/converting enemy generals, disrupting supply lines (less action points in tactical battle screen), that sort of thing. 

To reiterate, for me, the Quest and Adventuring system would take the place of an espionage system.

I think it would be good to have separate threads for quests and quests  coding mechanics.

I'll only talk of the latter:

XML is nice but limited and can be PITA to write. In writing a scenario for Fall from Heaven, I found that Civ's requiring about twenty seveen thousand billions of xml elements in every single quest entry, most of which were never filled, is evil. The xml should be limited as much as possible. It should ideally contain preconditions (like already solved quests or equations using only global game values, or the name of a python function to call in extreme cases), trigger information(which screen appears when quest happens), possible choices, delay for taking the choice, default choice if no action taken, optional geographic location/requirement, postconditions (screens/messages that will appear when/if quest is completed by player/by other player/by timeout), quest journal information.

And texts, obviously, in order to be able to translate them for instance, but in another xml file please.

Everything else, and as much as possible should be in python imo. Spawning units, having them switch sides, putting treasure on the map, should all be python. Otherwise when we need to do something clever that requires python coding, it will be endless back-and-forth between python and xml.

As expressed by others, there should be a quest journal. So that quests have a status (who accepted the quest), completion level, and messages pertaining to this quest can easily be found back. Fall from Heaven scenarios allowed some text down the screen for instance, but it was rather small and limited. Regular Civ IV quests were more elaborate and had a better interface, but the best quest  tracking stuff is found in journals like those of Fallout or Arcanum, although a per-quest filter would be definitely needed.

Quests with multiple outcomes are a plus.

*Booming Voice*

Quest: Find the Dragon Egg

Variables: Found within X turns starting from quest initiation till game over

1) D.Egg is recovered very early from player focusing much time and enormous resource expenditure to complete it.

Result: Player can hatch it, allow it time to mature in growth, and train it into godzilla with wings.

2) D.Egg is recovered late game, lazily.

Result:  Through technological research the player has found a way to convert it's vitae into a alchemical stat boosting drug for Y units of the players choice.  No time to hatch a dragon.

3) D.Egg is never recovered.

Result:  It is eventually reclaimed by the wildlife and gets hatched causing a new pest control problem for the local kingdoms.  Everybody loses.

I would like to see a few mainstream, big deal, big time quests that people are building to that have a large impact on the game.  I would like these quests to be open to anyone in the game to complete, or at least know about (the last thing I want is a dragon to wreck my city because I didn't research Advanced Lore so I didn't know that the "Aid the Ice Dragon" quest was available).

In fact, having a main story line initiated at the game's start, and having all of the quests move that story along, would be fantastic.  "Find the mystic statue" to "Protect the mystic statue/steal the mystic statue" to "Survive the evil warlord the statue summoned" would be fun and aid to the story telling of the game.

I really, really don't want a lot of little quests to micromanage.  I want big game changing stuff.

If the Sovereign were to be poisoned, there should be a consequence to not dealing with the poisoning (aka Death, ergo Game Over according to strict Frogboy Rules). If we suppose tat at the same time that posiong doesn't disable the Sovereign (would be OP and/or unfun), just imagine that random event/quest happening while you are in a dificult war. I'm all in favour of such quest if it means that there is an Spionage/Assasins system that caused it.

Altough people might hate the possibility of losing their Sovereign because of a random event/quest. Even if it gives the opportunity of saving him. (anything could go wrong during the quest, specially if your enemies know about it)

Don't know if anybody else already mentioned this (only read pages #1, #6 and #7), but competitive quests would be pretty cool. An event shows up, and the different players try to solve it, maybe using different approaches.

Example: a wizard comes up with research to some powerful spell. The players could either try to find him and offer him shelter to finish his research (maybe using some sort of auctioning system to win the wizard over) and then get access to the spell, or the players could try to assassinate him and deny everybody access to him in the future.

Another example: a treacherous NPC in a player's court gets angry with the sovereign and decides to seek exile in another player's castle, trading information for safety and luxuries. So one player would be trying to hunt the NPC down before he could betray some secret (like revealing the possession of a certain artefact or tech), while the others would be trying to offer him safety (and maybe risking being betrayed in the future).