Not those that cheated rather those that seemed to play the game really good. There used to be a WWIII simulation game for the super NES (basically Soviets verses USA) that was really good.
Even though Halo’s is pretty impressive, I still have to go with Nintendo 64’s Perfect Dark. The AI, both in single-player and multi-player is amazing.
For instance, in multi-player, you can’t simply camp and wait for the CPU opponent to run by and kill him over and over, because eventually he’ll stop coming and make you go to him.
I suppose IBM’s Deep Blue doesn’t count? 
I’m impressed with Hitman 2, even though I know the illusion of intelligence is achieved with deceptively simple algorithms. Nevertheless, when you’re dressed as a Russian soldier and moving through a Russian military base and you know you have to time it just right and not walk too fast because if any of them get a halfway decent look at your face they’ll realize they don’t recognise you and ask for your ID and then you’re screwed, your adrenaline is pumping and you feel like those are real people walking around.
I liked one of the first levels too, where the servant staff recognises the servant staff but not the bodyguards and the bodyguards recognise the bodyguards but not the servant staff, so if you’re in bodyguard clothes you’re safe from the servant staff but the bodyguards will shoot you on sight.
If they don’t accept the first pass you show them, just give them some Marks and they’ll salute and walk away, letting you shoot them in the back. Then you can search the body and get the bribe back.
Oh, wait, that was Beyond Castle Wolfenstein.
I’ll get the obligatory mention of Half-life in - the Marines were frighteningly good, particularly for the time.
The most recent Kyle Katarn game from LucasArts (Jedi Knight II?) had very good AI from the toughest bad-guys. I almost died from shock (and then Kyle /did/ die) when the first set I ran into were clever enough to spot my land-mine trap and use their force powers to turn it back on me. Storm-troopers are still as thick as two short planks, but then it takes a special kind of person to sign up to go into combat wearing bright white armor.
In a different genre, Sid Meier’s Pirates! can have good AI. Like JKII above, the toughest opponents (pirate hunters and naval vessels) often have very good sailing AI, taking advantage of the wind and their ship’s fastest tacks. The ground combat AI is limited, alas.
I seem to remember that Jet Force Gemini (N64) had some pretty impressive AI, particularly the cover recognition.
I remember being amazed when I first played Metal Arms: A Glitch in the System (GameCube, in this case) because team mates could actually follow you around effectively - you wouldn’t have to sit still every few seconds and wait for them to catch up, or get themselves unstuck on corners or whatever. They seemed pretty robust.
~ Isaac
Pac-Man.
No, really!
The bad guys all had different routes they ran.
Once they got within a certain distance, they started to close in, again, following different routes.
They would stop and wait for you.
They would turn and run before you became dangerous, then they would turn around and start chasing you again before you became harmless.
I read this on a message board comparing the idiocy which was Ultima Online AI vs. Pacman; there were several more things in there that the computer game industry had left by the wayside in favor of shiny special effects.
Not a game, but the Reaperbot for Quake was pretty damn good.
All the bots before Reaperbot for single player deathmatch were crap. Then the Reaperbot came out. I was so stunned when I first played it. It would run around constantly, like a real player. Switch weapons. Run away when low on health to pick up a first aid pack.
It may not be the best outright, but the AI in Thief 2: The Metal Age deserves a mention. In Thief 1, you could perch out of reach and shoot an alerted sword-guard full of arrows. I got a bit of a shock in Thief 2 when I tried the same thing, and the guard ran off and came back a minute later with a buddy who had a bow.
The varying degrees of alertness/suspicion were great, too. They had considerable effect on what you could get away with.
And that game was of course in more than one way inspired by another pretty clever game. MGS2, at its highest difficulty level, has some pretty sharp routines governing its baddies at times.
Of the more simple games, I remember Elemental’s AI (Atari ST) being tough as nails. Some of the enemies in Bitmap Brother’s Gods were also quite smart, ducking and jumping over your bursts and such, though mostly they followed a set path.
The Sims2 has the best I’ve seen so far, but then again I’m not much into the shoot 'em up’s anymore.
They all react to things differently based on personality traits assigned to them and previous game play.
They actually have a record of recorded memories that they can share with other Sims.
For instance, if a child Sim witnesses one of their parents cheating (let’s say Mom), besides reacting to it by crying and their relationship score going down, they get a memory marker of that cheat which means if they have a conversation Dad it could very well come up. If it does, basically the child just told on Mom, Dad reacts as if he witnessed it, becoming depressed, lashing out at Mom and dropping their relationship scores into the negatives (usually).
My Sims have been passing around the story of how my very first Sim, Betty, peed herself since the beginning of the game. Heck, Sims that don’t even know Betty knows she peed herself. 
If a Sim doesn’t like another Sim in the same room, it’ll show on their face and they may autonomously try to fight or tease that Sim.
A lot of the times, the Sim will stare “right at you” even if you rotate the camera view. They just turn their heads and follow you.
Also, if you have a Sim that is very sloppy try to clean, they’ll look at you and give you a “Why me?” look while pointing to themselves. Their shoulders will droop and they’ll sulk off to do what you asked.
A very neat Sim will actually become excited if instructed to clean.
They also have Wants and Fears. I’ve notice that if a Sim is enemies with another Sim, they’ll actually have the Want to see that other Sim’s ghost! Evil.
One of the coolest AI moments I ever saw was in Turok 2. I had shot an arrow at at a big, burly enemy, but missed and it his the wall behind him. Hearing the impact, the enemy looked behind him at the arrow, then looked in the direction it came in and found me.
That was so freakin’ cool looking.