Epic strategy games (or, 4X games) tend to have a similar problem. The start of the game is significantly more difficult and interesting than the rest of the game. Every choice matters at the start, but once a certain level of infrastructure is reached within the game, the human player will almost always defeat the AI. I wish I could come up with a clever term for this problem, but it's the main reason that I end up being more frustrated with games that are otherwise exceptional, such as Rome: Total War.
Civilization, being the king of the 4X game, has this problem as well. But the main reason I keep returning to Civilization's recent incarnations is its customizability. Civilization IV, in particular, was made for modders to play with on multiple levels. It's not as user-friendly as its predecessor, but much more powerful. So you get mods like "Fall From Heaven," which posits itself as a sequel to Master of Magic, and the fascinating "Rhye's and Fall of Civilization" (RFC).
"Rhye" is the screen name of the modder, and first achieved fame for his "Rhye's of Civilization," a Civ3 mod which demonstrated his gift of taking the basic concepts of the game, and making them more streamlined, historical, balanced, interesting, and, oddly, attractive.
The most important development for RFC, his Civ4 mod, is the concept of "stability." Stability, in-game, is basically the historically accurate acknowledgement that empires aren't always defeated by opposing empires, but often collapse themselves. The Mongol empire which exploded across Eurasia was not conquered by its rivals, but rather, broke into smaller pieces which were eventually absorbed by other political entities.
Stability also functions as a mechanism to keep the game interesting regardless of the player's power. Instead of merely competing with the insufficient AI, the player is forced to compete with the complex stability mechanism, which encourages infrastructure-building and measured expansion. In perhaps the cleverest aspect of stability, economic stability is tied to growth - and there's only so much growth possible short of founding or conquering new cities. Thus, a civilization has to keep growing (but not too fast) or end up stagnating. And if a teetering civilization happens to lose even a small border city, it can collapse.
There are still several problems. The stability model isn't terribly transparent. It can't be, really, otherwise it would be too easy. I do think that a happier medium could be found. New players especially are going to find it too abtruse.
The other major problem is that the penalties of collapsing stability are a bit off. Having a bad stability may mean that a city or two at random declares independence. Collapsed stability means that all cities, except the player's capital, declare independence or return to their original owner. There's not a whole lot of room between total collapse and slight annoyance.
Still, it's a major step towards solving the biggest 4x problem or being too easy after the initial part of the game.