For me it's not about making games harder, ideal AI is human-like AI. AI that will match and surprise you, not AI that has the intellect of a chessmaster, instant reflexes and perfect attacks.
Though I do like a hardcore type difficulty to be included in a game, just so the limits can be taken off the AI.
Someone mentioned Galactic Civilisations II, I remember that being praised for it's AI myself now. I have the game, but I've never been able to get into it to find out, but I remember reading some big articles on the game's AI, which is what made me buy it in the first place.
Some of today's game AI's seem either so dumb that they can barely even pose a threat to you at all, or have no more complexity to them than to simply charge at you. Or shoot at you when you come into range and not do anything else. Just dumbed down or underdeveloped so much. Play something like Streets of Rage 2 and crank the difficulty up on that and the enemy AI is pretty damn good and challenging. That game has surprised me on more than one occasion after playing some more modern game with inferior AI.
AI doesn't need to be complex, people praise the AI of the pacman ghosts a lot, but when it comes down to it, it's very simple, giving an illusion of intelligence. If you are under an illusion, it's just as effective as a complex AI. It makes you feel the same way about the in-game AI.