I have a few ideas, but I'm going to give them difficulty levels as well - some players should realize that greater rewards require greater risk and tactics, not to mention that quests should always be fun to accomplish on any level.

"They came from... behind!" [hard]
With the help of an elemental ally (one of the members of your element), surround/trap and duel/beat a player by fighting him on his original spot (see Battle Mechanics thread for clarification).
"Sightseer" [easy]
Visit X amount of Wonders within a round. By 'Visit', you have to simply be within 1 hexagon range of the Wonder in question.
"Greedy" [variable]
Nab several special resources found within the map terrain during XX turns.
"The Diplomat" [VERY hard, assuming players are backstabbers]
Find a way to have 3-4 or more players (of DIFFERENT elements) to share a rare or special space within one turn. None of the players can be attacking in order for this to be completed.
"Homesickness" [medium]
Return to your capital city every time you defeat an opponent, for at least X consecutive battles.
"Show Me Your Moves!" [easy]
Use all of the following moves within 6 turns without losing a battle: Move + Attack, Move + Defend, etc. (6 actions total)
"No Parking" [medium]
Hang around another elemental's capital city/'spaces' without fighting for at least X turns.
"Hypochondriac" [variable]
Whenever you lose a battle, always return to X spot. You must do this for Y lost battles.
"Bodyguard" [variable]
Choose an elemental ally or player to 'protect' for X turns. If they are killed/defeated in X battles within those turns, you fail this quest immediately (this does not include battles that they engage you in).
...
"~Somewhere Over the Rainbow" [impossible, but guarantees automatic win]
Conquer and obtain all of the Wonders for your Element. Elemental allies may assist with you in this quest. This quest can be replaced at any time.