I think for perfect information board games Go is the pinnacle, at least among the human-played. (the field of general game-playing AIs makes up all kinds of crazy games that might be "harder" in one way or the other)
If you look for an RTS game, StarCraft is an obvious candidate. It has a relatively active community of AI writers and AI competitions, it's a classic of competitive play, ...
Real-time games are hard to compare, because the interface really makes a difference. Does the AI get to talk directly to the game engine? Or does it have to use screen capture, understand the image and then use a robot arm to press keys, or something in between? If it gets to see precise positions and to input commands directly, even relatively "simple" programs can do crazy micro tricks and get massive advantages that way, even if their general macro-strategy is bad. If you do the other way you need image analysis and robotics, Google should have the tech for both ;)
No, after StarCraft they suggested 3D games (eg: Call of Duty, ...). Mind you, this is playing based on the pixels, not based on direct access to the game structures as bots do today.
The from playing Call of Duty to controling a robot with a gun in the real world it's a small step :)
I don't like the idea of FPS'. We'd expect them to behave the humans when they play FPS - they run looking forward and will occasionally look left or right and follow some predetermined pathing that they are familiar with.
With an AI, if we base it on pixels, what they will do is spin around 360 degrees about 60 times a second while moving forward so that it can maximize all of the pixels inputted at a time. It would compare it against the stored level design and shoot at anything that is off (or against character models). I can just see that it's not going to behave like anything we'd expect.
The same would likely be true of an RTS. An AI could scroll the viewport around and click units to issue orders at ludicrous speeds. Even if it had to use the same interface as a human, it'd still have a huge mechanical advantage.
Starcraft is definitely up there. No-limit texas holdem poker is also very difficult.
After that... then we have games that involve physical movement. Although I'm not sure what would be fair for strength & speed of robots vs humans. I'm imagining a team of robot soccer players, for example.
