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 ;)