Seems like you're conflating Smart AI with an optimal game playing algorithm. An aimbot isn't hard time create, sure, but it's not exactly smart, either. Nor is it fun. I agree it's harder to make mediocre but fun AI, and that's what current shooters do. The point is that there's theoretically a level above that, harder to achieve but not impossible, where the AI behaves like a human would. A reasonable balance of predictability and unpredictability, skill, strategy, but not perfection.
In a real time strategy, it seems we're approaching that level with that StarCraft ai. Need to perhaps restrain the ai's ability to micro by fuzzing it's ability to control quickly and precisely in bursts, and then continue to advance it's strategic ability, but I expect it'll get there eventually.
In the case of shooters. It might involve giving the AI a noisy view of the game world, to force it to approach the problem the way a human does. Humans don't just have an accuracy rate or a timer between an event entering their screen and their ability to shoot at it. A human has to filter through visual noise to notice a target, and decide how to engage. A human has to use an arm and hand and muscle memory to manipulate a mouse to get bullets on target. Those are all imperfect controls, with a certain amount of uncertainty between intent and action. All that is further influenced by how prepared the human was, how much they have to adjust their previous plans, or recenter their attention.
It's a difficult task to identify all the things that actually make a game difficult for a human and make sure the AI faces a close approximation of the same problems. Then it's even more difficult to get an AI to a point where it can compete on a human level, not to mention various human levels.
That doesn't mean it's not possible or not worthwhile.