Ogre had a really good AI. I found it almost impossible to stop that bleepin tank!
Empire had a really good AI. In fact, I'm playing Empire Deluxe on the other computer and I see it do fairly bright stuff all the time. It knows to hit land units near its cities instead of worrying about the other stuff. It knows not to attack battleships with loners. It sends fighters after my bombers. It defends good terrain and doesn't attack from rivers very often (which gives a combat penalty). However, I suspect that the AI in the original Empire was better.
EU and EU2 are pretty good, considering the vast quantity of things you have to do in the game.
I found the bots in UT to be pretty good, even if they could see me when I was invisible. The UT2 demo I'm playing now and then seems like it's got some cheats. I am convinced the bots know where I am at all times, because I have seen them turn around and attack me when I was in places they couldn't have seen me, and I hadn't fired at them yet.
The Q2 and Q3 bots, on the other hand, are not terribly good. I can easily set up timing so I snag stuff as it appears. I hardly ever get anything good in UT unless I work for it or it's located somewhere the bots just don't want to go.
I think the real problem with "modern" AIs is that the games are fairly complicated, the rules are changing all during construction of the game, and the AI programmers simply don't have enough time to work on it. If they had a full gameplan in advance, and knew exactly what to expect the whole development cycle, and utilized multi-threading, they could probably do a much better job.
Then skill levels could be based on AI brightness, not AI cheats.