This is going to be a "HURR DURR Old games were so much harder new games are for noobs" thing, isn't it.
EDIT:
The thing is, I don't really think we need "better" AI. It is trivially easy to set up AI code so that it will give players an unbeatable challenge (Also known as "Cheating in the AIs favour"). What we need is more "natural" AI. The problem is that as graphics and sound and storytelling have advanced to make games much more real, the deficiencies of the AI become that much clearer. In an environment where we can expect things to feel real, moments where an AI opponent will do something clearly nonsensical (Like, say, storming in front of the player's gun barrel) will stick out like a sore thumb.
Of course, once you try to solve this problem, you'll get to another problem, namely "How do I make this a fun game again, now that the AI can kick a given human's ass pretty much all the time". Sometimes (See XCOM), that sort of thing is expected and taken into account by the fanbase. But elsewhere? I am not so sure if "Make games hard again" is really a good thing to do.
I think what most of us would like is AI capable of problem-solving without cheating. Strategy games are great examples of this - SC2 (to choose a popular example) actively allows the AI to cheat to produce harder levels of difficulty. Without those cheating methods, AI is incapable out out-foxing a human opponent. Actually, this is one of my major gripes with RTS games in general - they often come down to efficiency and build order, versus any tactical or strategic-level thinking.
I agree that natural AI is the goal, but that requires the AI to actually be able to perform limited problem-solving; or for scripted sequences that trick the player into thinking the AI is problem-solving. All the games that get praise for the depth of their AI did exactly that.
Harder is not "better." Challenge is. It's easy to make a game harder - think of the lethal accuracy and damage ME3 MP's enemies put out compared to players - but it's not easy to provide a fair challenge. Anyone else tired of AI with ESP and auto-aim? I sure am. That said, it's also trivial to defeat because there has to be enough error built in to allow a human to win. Some balance is necessary.
I'm playing a lot of older games at the moment, precisely because their gameplay is often superior to modern games they inspired with better visual but less depth.