Garry Kasparov has an interesting essay about chess and AI here. In a nutshell, computers can beat most humans at chess, but solely through the use of brute force. There's no real intelligence in the AI. He even speculates, as I've often thought myself, that computers will eventually be strong enough to "solve" chess - to conclusively evaluate every possible move in the game. (Checkers, incidentally, was solved in 2007.)
Kasparov thinks that the game that can teach computers to think is Poker, because it's a game of incomplete information. I agree, but I think that go would also be a good avenue to try. Go involves a less linear style of thinking than chess, which is really hard for computers. I've read that the best go programs are routinely beaten by decent amateur players. (Not that I'd have a shot - I've barely played. According to this program I'm rated 19-kyu, which is the Japanese rating system equivalent to "bag of rocks".)
Maybe shogi would be a good intermediate step. It's very similar to chess in that it's a highly organized and linear game, but the piece-drop rule adds a bit of a go-like twist.