Sony - PlayStation 3, PSP, etc.
Madden's still a big deal, if you think he might like that. If he doesn't need to have the latest & greatest, you could get Madden NFL 10 for pretty cheap used, and even cheaper if you go farther back in the years. I don't know how much the complexity of the games has grown since the PS1 days. I don't think I've really played a proper football game since NFL 2K1 on the Dreamcast, so I can't help there. I do think one of Madden NFL 11's new features is to streamline the game by letting the AI do play calling for you if you like.
Civilization Revolution isn't an authentic representation of history, by any means. There is some progress through the ages as you build up technologies. But each populace is always represented by the same caricature of one of that country's more famous leaders. The US is always Abe Lincoln, England is always Queen Elizabeth, and so on. If you're not sure about it, there's a demo available to download on the PlayStation Store. The full title of the game is Sid Meier's Civilization Revolution, so it'll be under "S" if you go looking for it.
Using a Move controller might be easier for shooters for a beginner, just because you get to use the main controller (the one with the ball on top) as a pointer, which may be more intuitive, assuming it works properly. Killzone 3 comes out in February, which will have Move support.
Call of Duty 4 has a brief boot camp training section to start the game, which could let him get used to the basic first-person shooter mechanics. It also has 4 difficulty levels for the game itself. And it's a pretty nifty game, even if you don't play online.
If he doesn't mind moving away from a war scenario, you could try Portal, which comes as part of The Orange Box. You're not getting shot at, so he could fiddle around until he gets used to things. Plus, it comes with Half-Life 2 and its two Episodes, which are pretty great games. (And Team Fortress 2, which is mainly an online multi-player game, but apparently not all that great for the PS3 version.) It should be under $20, as well.
If he likes golf, Tiger Woods PGA Tour 11 supports Move, so he can essentially swing the controller as a club.
And there's all sorts of demos to download to give things a shot, including a handful of Move games.