Thief: the Dark Project. A kind of sneaky FPS, with a good IA at the time. The whole game was about not being seen or you probably die by a few axe hits. Really fun to play!
Actually, the AI is still impressive compared to the mindless drones inhabiting current games. The AI was fair and unforgiving at the same time, a perfect balance. Although in Thief 2 it was done better because the AI would go seek help more realistically, in Thief 1 it tended to just forget you were there.