2. Land Mines that would be visible to the civilization that placed them.
3. A stone tower with a statue of a gargoyle or other type of creature perched on it. The creature would not travel more than X distance from the tower and would animate and fight any enemies that came near it. It would be possible to safely blast it at a range with a catapult just like any other tower.
4. Upkeep on units and temporarily decreased stats resulting from units being too far from a supply source such as a Town Center, Castle, Supply Tent, etc. Supply tents could be built by traveling armies. This would help keep the "rush tactic" in check.
5. Also, millitary units could have an upkeep such as costing 1 gold each every X seconds/minutes etc just to have it in your army. For example, there is a reason why the United States doesn't keep a standing army of 150 million men at all times. Maybe millitary units could also doube as villagers to a point, except would just be so much more exepnsive than a regular villager.
6. Ability to pick an enemy unit type as #1 priority for individual units or possibly all your units as default to kill in battle. For example, your units will immediately focus on killing enemy catapult every time one or more are spotted. They aren't really looking for them, except if they see a catapult, they change what they are doing until they kill it or die.
7. Priests accompanying units make those units more resistant to conversion within a certain range.
8. I agree wholeheartedly with the suggestions for units on walls and manned turrets. Ladders used to scale walls would be awesome. As far as double walls are concerned, first your opponent has to spend the time and resources to build them and you have already forced him to alter his tactics. Afterwards, the ladders could be pulled down to the other side of the wall and used on the next one. Also, the fact that something's effectiveness has been compromised is not a reason to not include it. No one has to use it. It hurts nothing. The only reason to not include an optional unit is because it is too powerful and ruins gameplay by being cheesy.
9. Creatures that would require the cooperation of heroes from different civilizations to summon. For example, a Greek player would have to cooperate with his Norse ally to summon an NPC Gaia type of creature that would kill all Sphinxes in sight. I have no idea how this would be implemented, except I think it would be neat.
10. Domestication of animals and the potential to use tham as mounts. Wouldn't it be cool to be able to domesticate some hippos and make more of them. You could mount an army of cavalry on them and attack your opponent with an army of mounted hippotamus cavalry.
11. Allow villagers to dig into terrain and irrigate water.
12. Allow the construction of retractible briges.