My suggestions, ie what I look for in a strategy game.
A strategy presupposes thinking and planning ahead.
I am not sure how to best express my thoughts so please bear with me. There must be a variety of ways to win or put another way there must choices. There should not be choices that are so obviously superior to all others that it effectively becomes the only choice. The key point is that one must be able to plan a series of choices (ie formulate a strategy) which allow a realistic prospect of victory BUT there must be no strategy which guarantees victory. There must be a certain tension throughout the game, the possibility of defeat must exist at all times (except the last few turns of course).
There must be variety in the game. The strategy for each game must not be a carbon copy of the previous game.
Using Civ 4 as an example. Ones opening moves will differ depending upon terrain. Whether one builds a fishing boat, worker, scout or warrior depends largely upon ones starting location, traits and starting technology. Ones strategy depends on numerous factors including starting location, surrounding terrain, map type neighbours etc etc.
It is good to have a variety of options to allow differentiation of ones strategies however the AI must also be able handle those options. It would arguably be best to leave out features that the AI simply can not handle. (There is debate going on about whether Civ5 should have 1 unit per tile which the AI can not handle or retain the Civ4 stack of doom which the AI could use in a fashion). The AI must be able to put up a good show without excessive reliance on gigantic bonuses or cheating (OTH the braindead AI in Civ2 did cheat and had massive bonuses but it was a good game despite that).
Complex is good as it contributes to replayability. Complicated is bad as it leads to pointless messing about and makes it harder to program a decent AI. Repetitiveness is bad as it leads to boredom.
There should be "milestones" which allow the player a sense of achievement. Such as completing research on a new tech. If there are so many techs that a new one becomes available every turn then getting a new tech has no "oomph" for the player.