Non-FPS excellent AI: DF has already been mentioned, but an excellent DOS-based game that I used to play on my 386 was Commanche Maximum OverKill. (helicopter combat sim) The game proudly stated this in the manual: (bad quote from memory) "...with a smart AI that changes it's behaviour every 3 minutes..."

This stuck with me because it actually worked. If you repeated an action long enough, the AI changed how it tried to kill you.

Scenario: You are in your helicopter trying to blow up tanks and helicopters, and "Mission Targets". The lower you fly, the longer you evade radar, and the closer you can get to your target. So you hide behind some hills, pop-up acquire a target on a fuel tank, fire your missile, and then duck down before the enemy missiles can get to you. You then repeat this process to get all of the targets, but if you take too long the tanks/helicopters will fly around the hill trying to find you (as opposed to sitting next to the targets dumbly forgetting you exist).

The game learned from your pattern, and adapted. IMHO this was superior to every other game that just had the enemy shoot faster (i.e. Unreal Tournament)

On the other hand, it might just be nostalgia.