Some of these have been mentioned before, but I'll mention them quickly again (perhaps the number of people requesting a certain addition/change gives that item more weight).
1. Unit formations - at the moment they're all squares. I'd like to make a line of archers or a wedge of cavalry without the need for 20 different commanders and half an hour to individually assign each troop their orders
2. Amazons! Amazons! Amazons! I like the ones that we get from individual provinces, and would like to see them made into a full fledged nation. Early age, I'm guessing. Or perhaps Middle Age, when Sauromatia is no longer around, the Amazons could make a comeback.
3. Custom Pretenders - choose the graphics, choose the abilities and stats based on a point system, write a description all your own.
4. The ability to view battles from lands where my spies are hidden.
5. The ability to choose your own starting location when in single player.
6. The ability to back off from attempting to assassinate a target. Many times my assassins have been killed because they picked the wrong target. Perhaps a better way to do it would be to have a list of potential targets in the region and let the player pick which one the assassin will go after. Perhaps for balance, no more than one assassin can attack any one character per turn? Another balancing option would be to have a random chance that the assassin just doesn't get an adequate opportunity to attempt an assassination and therefore no battle that turn.
7. I know someone will horror mark me for this one

, but what about the ability to command units on the tactical level in a turn based mode, thus eliminating the need for orders and such? Maybe it could just be an option for those of us who enjoy micromanaging battles?
8. More spells and more research to do. Love the tech tree!
9. The ability to see and approve the random name generated for your Pretender before the game starts. This would avoid players getting unwanted names for their gods.