Most of the X-Box Live Arcade Line up is pretty good, I know they may not last as "long" as some of the normal titles are concerned, but some of the games are great.
Lego Star Wars : The Complete Saga is 2000 times better then Lego Batman, heck, even I couldn't beat one of Lego Batman's bosses. I just didn't know what to do.
Most racing games are good, also look at the Indie game lineup. Some of those games are good, and quite cheap. And the best part, depending on how you look at it, have VERY basic game mechanics and a look to them. For instance, if you eventually want to bring him into a shooter game, Try out Avatar Laser Tag, The game is "horrible" from a older person perspective, (the trial version lets you test it) but It is basic enough for a kid to possibly find joy in it and provide basic concepts for playing that sort of game.
Ill post more after I look around some more.