Just some quick thoughts that have sprung up regarding having the game become more challenging as it is played.
One source of information that I don't recall seeing in the (admittedly limited) TBS/RPG games that I've played is having the game capture data as people play the game and then incorporate those experiences into later attempts - basically a learning AI. These are just some quick thoughts meant to inspire ideas but that do not consider computational resources.
1) Localized Learning - have the game adapt directly to the player to increase the challenge/realism level.
2) Global Learning: Allow people to have both their own PC as well as NPC data transmitted to Stardock where it is then analyzed to create new AI structures that can then be downloaded by others and incorporated into the NPC AI
Some expansion/examples:
Biological Classification Scheme
In many RPGs you have character stats that, in effect, help to define the class of the character. In addition to pre-defined character classes the game would see what kinds of classes are being created by players and would be able to add those options dynamically to the "cannon classes". From an implementation standpoint you would track PCs from level 1 and, using their initial stats and other data watch how they progress in level (what skills, attributes, etc. they choose). Mapping these and forming statistical classification methodologies (i.e., like biology uses for classifying species into phylums and such) you would be able to identify different classes and then have them named, refined and included on the resources server. NPCs would then use those as guidelines when levelling up as well as when they purchase equipment.
Research Choice Influences
Another setup would be to capture statistics whenever a player chooses to focus and try to infer/model the pre-conditions that led to the specific technology choice. Then, the AI, when faced with research options, would be able to compare its state to others and, if they "match" would then be influenced to pick the same or similar technology (and ideally use it in similar fashion to how the player used it).
Changes in Disposition
The last thought is more general in that certain points in the game lead players to evaluate and possibly change their behavior/disposition. For instance, initial dispositions occur at game start and then change once the first magic shard is discovered, the first opponent encountered, and if they players sees a huge stacking marshalling near enemy borders. Putting special emphasis on capturing information at these points and the turns following would then allow the initial reactions and follow-through to be encapsulated into various AI algorithms and distributed in the canon resources.
Implementation Thoughts
To some degree that can be incorated into a manual process whereby the developers would look at the data and code new AI algorithms; but the cat's meow would be to incorporate learning into the AI engine (both local and a shared engine) that would be able to process these outputs and incorporate them into future games and distinct resources. Players would have the option to "reset" the AI and thus not consider any local or global knowledge; or even just reset one or the other. With the global data even a new player could quickly increase the challenge level without giving the AI super-powers. Just keep in mind that you want to learn good and bad behaviors since not everything a human does is going to turn out well. Having a "role-playing" flag for the human would also be cool since the human could role-play and thus teach the AI specific behavious that may not be optimal but would help to add to the flavor of the game. You would need to be careful about what data you accept when it comes to "role-playing" since if someone doesn't role-play well it can skew the results. But even if you were to only use it internally it would allow the end-user to choose between "challenging AI" and "flavor/RPG AI" which would broaden the interest and replay value of the game.
