I think Malachi256 has a good point. Although I don't buy into the current industry AI type ("AI will solve everything! Our AI products are great and you must have them!"), having an appropriately challenging AI in strategy games does make a difference. And, IMO, Civ IV is the high point of the series in AI. One can debate economic management, but especially in terms of managing warfare, the AI has never quite recovered from the move to 1 UPT. My opinion is VI is less bad than V in that regard, but the Civ IV AI remains a much more dangerous opponent.
I don't think the current AI hype is really the answer either, but incremental improvements that haven't happened since the mid-2000s.
As for complexity? Preference on complexity of the game vary, but when looking at it from an AI perspective, a key question is, "can the AI effectively make use of the complexity added to the game, or will it be a pushover?" If a new feature is added but the AI handles it incompetently or ignores it altogether, the game has been made easier for the human player. 1 UPT is again a good example - added because the designers thought it would add depth, but in practice it hasn't worked out well in terms of the AI handling it, so it's made the game less challenging. But there are others. The adjacencies of districts and improvements placed on the map. Arguably fun mechanic but if the AI makes poor use of it, the game's easier. The use of airplanes. Choosing effective policies. I'm not saying the AI is necessarily bad at all of these, but that if you have 40 mechanics in your game, the AI needs to be competent at most of them in order for it to provide a good challenge. If you only have 12 mechanics, it's relatively easier to reach a similar level of AI competence. And I could see the argument that while perhaps Civ hasn't reached the ceiling on complexity for humans, it may have for the level of AI effort that Firaxis has put into recent iterations of the series.
I'd love to see it reach the point where the "AI difficulty" was also affecting how many of those mechanics the AI pursued, as opposed to ignored. If Deity level was, "The AI does its best in all matters, while still playing fair, and you will have a very tough time winning", and each level below that neutralized some of the AI's evaluation capabilities, it would make for a much more interesting difficulty level progression for players.
It has been attempted before as well, I remember Galactic Civilizations II in the mid-2000s had options along these lines for its AI. I've seen it applied outside of the strategy genre as well - in the game Killing Floor, the AI opponents will shield themselves much more effectively on Hard difficulty than Normal, so you have to alter your tactics a bit to be effective, not just use the same tactics but with more enemy hitpoints. I think there's a lot of potential for Civ along these lines. If I win and turn up the difficulty, and all of a sudden the AI is much better at science production, or defends its borders more effectively, or starts making naval or airborne invasions that it wasn't at the lower difficulty, I have to think and strategize more about how to counter it more than if it just did the same thing as before but with more resources.