I like all suggestions that have popped up so far a lot. However, I have some small contributions to make:

1. I'd like to see heavy penalties for all kinds of missile units when fighting in a forest.

2. I'd like to see situational modifiers matter more, especially downhill fighting, tiredness etc.

3. I'd like to see either a) Archers firing faster or b) Crossbowmen firing more slowly.

4. I'd like to have the campaign map AI give the Mongols some concrete goals, which they try to reach no matter what, as well as a generally more aggressive behavior. In a recent campaign of mine, they didn't attack a single settlement, didn't attack other AI armies parked right under their nose. However, they made slow (ca. half movement points used per turn) progress into the Balkan area, until finally I stumbled over them at Venice. Then they ambled back east, only to wander off into Greece (which I wasn't interested in, so I left them alone). This is just ridiculous!

5. Rebels popping up all over the place may be interesting in the beginning, but from the point you have ten provinces, it just gets more and more annoying. Tie rebel frequency to size/stability/power of an empire, please! Alternatively, give us some real rebel challenge: When there is unrest in a settlement, let a stack of rebels pop up. When there is more unrest, let this stack multiply... and let it move and attack the settlement itself, instead of just standing around until the player gets annoyed enough to finish them off: Proactive rebels!