English teachers usually appreciate narrative. Here are some of the greatest stories ever gamed, and no spoilers, but dialogue cues (yes, I'm geeky that way):

Half Life (1998). "Wisely done, Mr. Freeman!"
Max Payne (2001). "A bit closer to heaven."
Devil May Cry 3 (2004). "Your father was a handsome devil, but you're no slouch yourself."
Metal Gear Solid 3: Subsistence (2005). "Kuwabara, Kuwabara..."
Final Fantasy 12 (2006). "You've let your eyes betray your heart."
Metal Gear Solid 4: Guns of the Patriots (2008). "Solidus must have taken the day off..."

FF7
FFX
Kingdom Hearts 1
Kingdom Hearts CoM
Valkyria Chronicals
Persona 4
Uncharted

I agree with him...  Books > Movies > Videogames

for the most part video game story telling it bad.  It's just that the bar has been set so low for the genre, that anything halfway decent is considered "great."  So many of them are filled with cliches or just not very good imo

Very few videogames have stories I'd consider great.

Anyway, here are the ones I thought stood out:

PC:
System Shock 2
Grim Fandango
HalfLife
Starcraft/BroodWar
Baldur's Gate II
Deus Ex
Fallout1/2
WarcraftII/III
Planescape Tourment

7th gen:
Mass Effect
Bioshock

6th gen: 
KoTOR (although I think we consider it great becasue it was better than the terrible new Trilogy)
Beyond Good & Evil
ICO
Shadow of the Collossus
Suikoden III
Final Fantasy X

5th gen:
Resident Evil (in a charmnig "B" movie kind of way)
Suikoden II

4th gen:
Chrono Trigger
Super Metroid (although it's really just the same of the first)

3rd gen:
Kid Icarus
Metroid

No praise is high enough for this game's story, any self respecting fan of the RPG genre that hasn't play this game is doing themself a deservice, its certainly better than ANY story from a JRPG and as good as most critically acclaimed novels I've read.

Glad to see a fellow fan :D

Thanks for your replies everyone, I'll be compiling a list and sending it off to him today. I'll post the list in my original post for your viewing to see what we came up with when I'm done.

FFX
MGS4

Both of these games were perfect gameplay was awesome and stories blew me away!!!!!!

Well First off I have to give props to areseris because system shock 2 has both an awesome story and narrative. but I also have to say why the hell hasnt anyone mentioned silent hill 2.

Of all the silent hill games (which have great story and narrative) silent hill 2 is the best. Personally I haven't a better story in any games except for maybe MGS 3 (which has been mentioned).

Definitely silent hill 2

Where the Hell is Halo on this list!! the halo universe is extremly deep and very enthralling easily one of the best games ever. The games barely scratch the surface you need to read the books.

Really? I find Halo to be one of the more generic and cliched stories in the industry (Although there is far worse, unfortunately), exactly the opposite of what the OP is looking for in compiling his list.

And I should not have to read a book to understand a videogame .