Before I start this, I want to mention my favorite TBS games so that I can use them as talking points: Master of Orion II, Age of Wonders, and Fall from Heaven II (I won't play Civ IV any other way).
I was trying to think what my favorite features in my favorite TBS games are that are not in Elemental and I finally figured it out: faction (race) differentiation. Every time you play a different race in the games I mention above, the game plays VERY differently.
In MoO2, for example, you can play a race that lets you bypass the process of creating ground troops (with Telepathic), you can play a race that doesn't require food (Lithovore), you can play a race that gets 50% bonuses to research / income (Democracy), etc..
In Age of Wonders, each race has an entirely different army. This example isn't incredibly relevant due to the differences in the game types, though.
In Fall from Heaven (not that I need to tell Derek about that... But I'm going to anyway, please forgive me
), each race has crazy abilities that make them play very differently... Some examples: the elves create forests around their territories, can mobilize the trees as treants, and get bonuses while in the forest; there's another race that focuses on mages and can build a dark portal type thing that randomly spawns demons to serve them; yet another race can't really build healers but researches rituals which can turn their god-emperor into the strongest unit in the game.
Admittedly, I don't have the design skills to rework all of the races, but here are a few examples of the types of thing I'm talking about as they apply to Fallen Enchantress:
1. Capitar gains the ability to bribe humanoid armies into their service on the strategic map. Gold cost is based on strength of the army. Their other ability (Legacy of Cerrane?) would need to let them generate more money than it does right now so they could actually afford to bribe enemy armies.
2. Umber's Serpent's Pact allows the faction to build a special building in their cities that will randomly generate serpentine soldiers (e.g., 10% chance per season to generate 3 ophidians). The strength of the NPCs generated should be based on city level. Endless Legion should synergize with this by reducing the maintenance cost of armies.
3. Kraxis cities and outposts receive free city walls and an extra defending militia.
4. Gilden's Master Smith ability allows them the ability to create Masterwork versions of all the weapons & armors they've researched (in addition to the regular versions). Masterwork equipment costs twice as much to make but is 50% better. I'd also like them to have a spell or innate ability that let them locate Gold, Metal, and Material nodes on the map, beyond their normal line of sight, it could be "Prospecting."
5. Pariden has The Decalon (an actual item in the game) which will occasionally provide a boon to the faction or carrier. Sometimes, it's a free piece of technology, other times it's a free spell, bonus exp, stat boost, etc.. Each type could have a bit written up so "By translating the ancient work of Ezmir, you..." They would also keep the 10% research bonus.
I think that creating more distinct factions will do a lot for the game and will be far more noticeable than AI changes or stuff that's behind the scenes.
Any thoughts?