Fear 1 would be an example for a game with a good AI. Also Far Cry 1. Can't remember on a strategy game with a really good AI though (maybe Heroes of Might and Magic 3?).
I don't think any of the games above had good AI - but rather, they had believable AI.
I once read this piece by one of the AI programmers on the Halo series (can't for the life of me find it now) where he goes into the difference.
A good AI will be able to beat you time and time again using ingenuity and creativity. But such AIs are rarely fun. Instead, we prefer AIs that merely give the illusion of competence (e.g., they take cover... but always behind predictable objects. They flank, but always in obvious ways. They retreat, but always under specific, easy to understand conditions.). What the AI does is utterly predictable, but still challenging.
An unpredictable AI will quickly become frustrating instead of fun, even though it would be more realistic.
On the other hand, the predictability of the AI of RTS-Games (and the Civilization-games) gets critized quite often.
A good AI is a believable AI, in games. The AI of a game shouldn't be too powerful, the player has to have a chance to win. But predictable? I agree that the AI shouldn't be incomprehensible. The player should be be able to predict some moves. But if it really is utterly predictable, it is also frustrating.
Take Greedcorp as an example - or chess. If the player would never be baffled by the move of the AI, it would be no fun at all to play against them.
PS: But believability really is important. I always hated the moment in late-game of civ when conquering cities of advanced civilization with nothing in them but a temple. Always made it look like the AI doesn't even build properly and only can compete because of cheating, which repeatedly destroyed my motivation to beat the game.
