(Please avoid giving away any spoilers)
So in my English class today, the subject of video games came under discussion. My english teacher considers himself to be a tech savy person who enjoys video games, though I don't think he is fully a part of the video game scene (He thought the Final Fantasy series was only up to FFIX or FFX). While we were discussing them he said he didn't think video games were fully up to scratch in the storyline department, and were often filled with cliches. He asked if anyone could think of any good ones, myself and a few friends quickly rolled off the ones that came to mind first such as Final Fantasy, Bioshock and Fallout.

But  I can't just let him go on thinking that all video games have shit storylines and I want to tell him about a few more. So I decided to make a thread and ask you what games you think have really good story lines that aren't very cliched

So, what are some games that have really good storylines? Maybe say why - was it really confusing, or really gripping?

When we get enough, I'll send a list off to him.

Edit: If you could list the console(s) the game is on if the game is on if it's kind of unknown, that might be useful too.

It doesn't matter how old or new they are.

Okay so here's what we came up with. I added some of my own, and some I found in other 'top 10 lists' or whatever.

Assassins Creed

Bioshock

Braid
Portal
Hotel Dusk: Room 215
Suikoden 3

Chrono Cross

Chrono Trigger

Dues Ex

Fallout 2 
Beyond Good & Evil
Planescape: Torment

Final Fantasy IV

Final Fantasy IX

Final Fantasy VII

Final Fantasy VII: Crisis Core

Final Fantasy VIII

Final Fantasy X
Uncharted: Drake’s Fortune
Elder Scrolls IV: Oblivion

Final Fantasy XII

Fire Emblem series

God Of War II

Grim Fandango

Half-Life 1

Half-Life 2

Kid Icarus

Kingdom Hearts

Kingdom Hearts Chain Of Memories

Kingdom Hearts II

KOTOR 2

Lair

Legend of Zelda: Majora's Mask
God of War

Longest Journey and Dreamfall
Breath of Fire V
Fallout 1

Max Payne

Metal Gear Solid

Metal Gear Solid 2

Metal Gear Solid 3

Metal Gear Solid 4
Starcraft & Starcraft: Brood War

Metroid

Metroid Prime

Metroid Prime 2

Metroid Prime 3

Monkey Island

Persona 3

Persona 4
Ico

Phoenix Wright series

Planescape Torment

Resident Evil Series

Resistance 2

Resistance: Fall of Man

Shadow Hearts 2
Grandia Series (Apparently not so great, but the person who recommended it liked it)

Shadow Of The Colossus
Mass Effect 
Lunar SSSC

Silent Hill Series

Suikoden 2

Suikoden 5
Shadow Hearts 1

Super Metroid

System Shock 2

The Legend Of Zelda: A Link to the Past

The Legend Of Zelda: Twilight Princess

The Theif

Tom Clancy

Valkyria Chronicles

Valkyrie Profile 2: Silmeria
Valkryia Chronicles
Folklore
Phantasy Star Portable
Star Ocean: Till the end of time
Star Ocean: The Last Hope

Warcraft Series

Xenogears

Xenosaga
KOTOR 1

MGS3

The story was great, it never really slowed down and it all fit together pretty well. Made me keep playing until the credits.

Edit: There is also some controversial concepts in the story, such as whether ones own personal aspirations are more or less important than everyones as a whole and how far one should stray from their own path for their country.

Off the top of my head:

Starcraft & Starcraft: Brood War (has really good voice acting too)

Legend of Zelda: Majora's Mask - very cool that they took a series that had one of the most formulaic storylines of all and created something completely different for this game.

A lot of stuff in the point-and-click genre, like Day of the Tentacle, Beneath a Steel Sky, The Dig.

well first of all your teacher is somewhat right Novels are generally better than movies and movies are better than Video games in terms of story telling and evoking emotions

I remember when people flipped out when Jaffe said that the MGS story can't compare to some of the great movies and he is actually right

now to your question

God of War has a very good story about Greek mythology and magic

Bioshock has a very compelling story about a society experiment gone wrong

the Warcraft series

Ogrebattle 64. It's about a guy who just out of training joins the military. He joins the southern region which is pretty much the slum area of the country (it's split into 4 regions). THey begin quashing a rebel uprising. But it turns out he disobeys his commanders orders and right before they execute him he cuts off his ties. He then becomes a general in the rebel army and wage war on Palitenious.
The game continues on to involve another country called Lodis who is pulling the strings behind Palintenous's actions. You also have to deal with the creatures from the Netherworld. It's much to complicated to explain but you'll wet yourself when the credits roll.

I'm going to stick with this generation. The following four games I feel stand in a league of their own storywise:

Bioshock
Braid
Portal
Hotel Dusk: Room 215

I haven't played Flower yet but I hear it tells a better story through gameplay than almost all games have told through thousands of words and hours of cutscenes. Vagabond swears by it, which is what got my notice.

Oh dang...

If we can go back to the PS1 gen, there are quite a few with decent stories. Cliches are hard to avoid though. I definitely agree with your teacher on that point.

Here are a few real quick... (Cliches abound, but that doesn't necessarily detract from all game stories, imo)
Suikoden 3,5
Shadow Hearts 1,2
Grandia Series (Lots of people disagree with me on this one but I feel compelled to list it anyway :P)
Xenosaga
KOTOR 1,2 (Especially #1. Sith Lords kinda left a cliff hanger at the ending but it's still worthy)
Persona 3 (haven't played 4 yet, heard it's better)
Ico SotC (it's a different kind of storytelling, just as epic)
Mass Effect (The story really grabbed me. Loved it.)
MGS series
Lunar SSSC (Heard it's amazing from multiple people, haven't played it yet)
Longest Journey and Dreamfall
Breath of Fire V
Fallout 1,2
Warcraft 3 & Frozen Throne (Wicked story and cinematics)
Beyond Good & Evil
Planescape: Torment (Haven't played it yet but EVERY single person I talk to who owns it praises it's amazing character development and story)
Valkyria Chronicles

Chaos Legion.

Valkyrie Profile 2: Silmeria.

Valkryia Chronicles.

Folklore.

Phantasy Star Portable.

Star Ocean: Till the end of time.

Star Ocean: The Last Hope.

Final Fantasy Versus XIII.

You do realize the OP is looking for suggestions right? So obviously you pushing FF Versus XIII down our throats as a great story when we all know it's not even released yet doesn't really help out.

I know, just had to thorw that in there in case he wants to play the best JRPG this gen later on. :P