I think it would be a shame if elemental ended up being one of those games were a few playthroughs with a certain race immediately blazes a path of "only effective strategy" through the entire opening of the game. the galciv 2 planet rush comes to mind? Of course this is a broad generalization, but what I really want is something that challenges the min-maxer in my brain, so that every time i boot up a game with the same race against the same opposition, the experience, decisions and strategy would be different than the last time around.
ways to accomplish this:
1. have a lot of semi-random actors on the map, be it, places to visit, resources, adversaries, constraints... let the map change in some ways continously as part of the gameplay. A cool random map generator, and a dynamic map would go far here.
2. Have events in the game that are based on non-disclosed algorithms, that keep the events sensible and relevant, but keep the player from knowing when/if they show up. Examples: heroes join a player based on his actions or/and stats. Dominions 3 has huge amounts of events based on the players stats, that really keep every game new and interesting.
3. Have entities, other than the adversary, that are completely AI controlled, or can only be guided in some direction by the player. example: barbarian cities in civ 4. lesser civs in galciv2. in elemental this could be gods that you could ally with, who would give you tasks, but reward you for cooperation and gifts, while punishing you for the opposite.
Of course these ideas are meant for a single player experience, since the more randomness you introduce, the more difficult it will be creating a "balanced" multiplayer game, unless of course you make these things configurable. Unfortunately, the idea of "perfect balance" is what really makes it impossible to create a game that is both amazing in multiplayer matchups, while retaining long time single player replayability.