Harry Potter and the Philosophers Stone...
No seriously.
I haven't played a lot of games with a decent storyline (or any storyline for that matter) but for me it's Wc3 (mostly RoC) and Halo.
The fact that it's a game based on a movie based on a book helps.
Love.
Ever 17 - The Out of Infinity: I don't think you can really call it a game, because it's just a visual novel (i.e. dating sim), but if you like anime/manga and you like brick-shitting-level plot twists, then this is for you.
Other visual novels of the sort that are equally awesome (but contain pr0n, though in the English translations of these, you can choose to remove the one or two pr0n scenes in each storyline) are Tsukihime and Fate/Stay Night.
Tales of Symphonia: It's just really nice.
Deus Ex: Awe-inspiring in every aspect, including, but not limited to, gameplay, aesthetics, and, more importantly, storyline. Cyberpunk + Tinfoil Hat Conspiracies = AWESOME!
The game even fucking predicts 9/11 before it actually happens, which, though not necessarily related to the plot, is pretty creepy and amazing.
http://en.wikipedia.org/wiki/Deus_Ex said:
During sections of the game where the New York skyline is visible in the background, the two towers of the World Trade Center are noticeably missing; the real towers were destroyed a year after the game was released. Harvey Smith has explained that due to texture memory limitations, the portion of the skyline with the twin towers exists in the game's data files but had to be left out of the final game, with the other half mirrored in place of it. According to Smith, during the game's development, the developers justified the lack of the towers by stating that terrorists had destroyed the World Trade Center earlier in the game's storyline.
Starcraft: Notable because it has the most interesting plotline of any RTS I've seen before. Warcraft was pretty boring in comparison, and already had traces of storyline from Starcraft in the first place.