I like random events. Random events are good.
I want there to be a slider for the chance of a random event happening per turn. Minimum would be zero, maximum would be 5% or so. The slider will go in jumps of 0.5%.
Ideas for random events:
A) Quests (like in civ4). All players get the quest, the first to coplete it get the prize.
1) 'First player to build 12 forges gets the prize'.
2) 'Slay the Dragon (and loot his horde)'
B') Political decisions.
1) 'Your settlers have encountered a tribe of natives what shall we do with them?', where you need to choose a course of action, like 'enslave them'/'slaughter them'/'assimilate them'/leave them alone'. These kinds of events should have consequences, forcing the player to choose between short term bonus to long term bonus.
C) Map changes.
1) Large map area is being changed plains-->grassland or hills-->mountains.
2) Discovered a new resource.
D) Complex. Here's an example I would kill to see implemented.
'A scout barges into your throne room. He informs you the the great blue dragon Cakhol'amok has been sighted near the hamlet of Mulenheim. What are your orders Your Excellency?'
Options available: 1) 'Send the troops and dispose of this vile reptile' 2) 'Send a cart with {specify amount} of gold to the wyrm' 3) 'Send a messanger to the creature, and invite him here to see me'.
If chosen option 1, you get an Elder Blue Dragon near one of your hamlets.
If chosen option 2, depands on the amount you sent, he will either accept the tribute or attack you.
If chosen option 3, depands on the streangh of your empire, the dragon might actualy come peacefuly. You can then negotiate with him for his services/protection.