To echo ERP's comments:
When people say they want "better" AI, they don't really mean they want "better" AI.
They do not want an enemy that is harder to defeat.
They do not want a bot with inhuman aim.
They do not want an AI that always knows where you are and perfectly anticipates where you're going to be next and what you're going to do.
No, what they really want is:
1. An AI that doesn't look stupid.
Running into walls, being unable to find their way around an object, stuck in loops, getting stuck on geometry, saying the wrong thing at the wrong time, ignoring player actions, all of this makes your AI look stupid.
2. An AI that doesn't do impossible things.
No clipping through geometry, no being able to see you when it shouldn't, no hits coming from impossible angles, no visible cheating.
3. An AI that is mostly predictable (but occasionally surprises).
If the user can't figure out the internal state of the AI, then he's just going to assume it's actions are random (and thus stupid). This means your state machines need to be simple enough for the user to understand them through the feedback systems available to them in the game (sound effects, animations, voice samples, etc).
This is actually kind of counter-intuitive -- you'd think more complex AI would give you more believable behavior, but this isn't always true.
4. An AI that is plausibly fallible.
In the end, the whole point of the game's AI is NOT to beat the player. The goal for game AI is to give the player a good fair challenge, but in the end, the AI must LOSE in the most entertaining way possible.
If the AI never loses, the player will decide that he's not having fun, and call the AI unfair.
If the AI loses too easily or in an implausible fashion, the player will decide he's not having fun, and think the AI is stupid.