First games that come to mind

[Kikyoo]

1: Dark souls My favorite game. A throwback to the good old days, tho not nearly as punishing. Still I can't help but throw this one out there.
2: Dragon's Dogma This is a great game. One of the best to come out recently. I enjoyed it a lot and if asked, It would be in my top 3. It's also one of my favorite games.
3: Guild wars 2 As much as I hate to admit it, I would have to recommend Guild wars as a great place to get into an MMO. It's buggy as hell, but it is a lot of fun with a lot of variety in it.

If they are just dead set on a shooter game tho then ...
#1: X-com: Maybe find out if they are into turn based strat? I dunno you'd be surprised what people can get into.
#2: Saints Row the third: Third person run and gun shooter. While I think 2 was much better, I don't like sending people back for older games. Try to think progressively as possible. Keep it at least Semi fresh and new.
#3: Red dead redemption: This does not make any of my top lists, but a lot of other people really liked it. So I would recommend it for others to try, but not for myself.

Games I would not recommend but I like a lot?
1: Monster Hunter. The slowness is going to turn off people who are not really interested in the game. It's a hard game to get into.
2: Pokemon. A lot of people like this game, but if you recommend it to someone they are going to doubt everything you say afterwards. Personal Bias will work hard against you, so just leave this one alone.
3: Fire Emblem. I love this game, but dear lord it will punish you for going into it half hearted. A master of fire emblem must have the most serious of minds. The deepest of commitment. It is not forgiving and I can't really recommend it to anyone not willing to just get their head pounded in by it.

 

[BiggyShackleton]

Timesplitters 2 just to ease them out of milshooters and still experience something genius.
Then onto Majora's Mask.
Finish with Shadow of the Colossus.

Admittedly these are just three of my favourite games ever. Fuck it, they need to be experienced.

 

[Ieyke]

Assassin's Creed 2
Okami
Megaman X
Super Mario RPG:Legend Of The Seven Stars
Diablo 2: Lord Of Destruction
Donkey Kong Country 2iddy's Kong Quest
Portal
God Of War
Final Fantasy Tactics:War Of The Lions
Arkham City

 

[JEBWrench]

Of course. How could I NOT offer an ASCII game.
In fact, I'll go a step further and get him to play ZORK!

Be sure to recommend he get one of the re-releases with feelies! Because nothing says Infocom like feelies.

 

[Faux Furry]

Some of the first games off of the top of my head that are dissimilar to Call of Duty to recommend to this pretend friend?
1.Breath of Fire.
2. Dragon Age: Origins.
3.Dragon's Dogma.

Okay,I've got dragons on the brain right now. I'll try again.

1.Kameo: Elements of Power.
2.Faery:Legends of Avalon.
3.Tingle's Rupee Land.

Ah,nuts. Now its fairies. Thinking of nuts and creatures who like to consume them...
1.Conker's Bad Fur Day/Live and Reloaded.
2.BlazBlue: Continuum Shift Extend
3.Mr. Nutz.

 

[MASTACHIEFPWN]

Garry's Mod
The Human Revolution
Mass Effect 2

All of these games have left a huge impression on me.

 

[Grey_Focks]

Going on just my three favorite games at the moment, that'd be Dark Souls, Skyrim and XCOM. Two out of three of those aren't exactly noobie friendly, so I'd probably recommend something along these lines.

1)Skyrim, since it's pretty, not exactly difficult, and rewards faffing about. One of the noob-friendliest RPGs since Pokemon.

2)Starcraft 2, while the online community is one of the most intimidating out there, the campaign is actually really good and the game as a whole does a great job of teaching someone who's never seen a mouse before how to play an RTS. Not to mention his twitch reflexes from CoD would actually translate very well into micro-managing in this.

3)Something Mario, preferably one of the newer ones, since recommending old school games to people who haven't really tried anything outside of their comfort zone can really backfire. Mario may be the exception, but even then I'd try him out on the Mario Galaxy games.

Alternatively, I'd just invite him over, let him dick around with your collection so he can see what genres he likes, and then make recommendations from there.

EDIT- Oh hell, how did I forget about Portal? I'd prioritize that over Mario, but really, just make him play a bunch of different games, and see what interests him the most.

 

[Gmans uncle]

Mario Galaxy
Super Meat Boy
Portal 2
Rayman Origins
Banjo Kazooie

By the way, I've never played a COD game, and I hope to never change that, they look like all the worst things about moden games concentrated on a disk.

 

[Professor Lupin Madblood]

- Spec Ops: The Line, for what I hope are obvious reasons.
- The Thief series (or just Thief Gold, if you want to limit it to one game)
- Infamous and Infamous 2 (as above, not counting the second if you want just one)

Those were the three I thought of instantly. If we're allowed to give additional suggestions, I'd definitely put Zeno Clash on there, since it's hugely weird and hugely fun, as well as completely different from CoD.

 

[Ed130 The Vanguard]

Dishonored

Team Fortress 2

Bastion


No it isn't too strange for cell shaded games to be on the forefront of your mind. Their graphics tend to age better than the 'realistic' games.

 

[dimensional]

Valkyria Chronicles
Skyrim
Portal

Three games that are pretty different to call of duty but hopefully not so much that it will feel alien on all levels.