Lot of great recommendations in this thread, and I'm sure The Madman will come along sometime soon and post some 5 paragraph essay on great games that will change your life, but until he gets here let me add some that have been forgotten:
Arcanum: Of Steamworks and Magick Obscura = A steam-punk meets high-fantasy, and when I say meets I mean they are duking it out for supremacy. Seeing the standard fantasy races in industrial aged setting with interesting characters and plot to boot is just something so unique you can't pass it up.
Longest Journey = Adventure game with a non-stereotyped and
interesting female protagonist. It's rough, emotionally, but well worth it. Quite the.. pardon me, adventure. One of the best stories in gaming, still.
Vampire the Masquerade: Bloodlines and Redemption = These two games (Bloodlines and Redemption) play VERY differently, but both are set in the bleak yet fascinating world of darkness, through the perspective of the (duh) vampires. Redemption is a little heavier on the story as opposed to reveling in your vampire badassitude like Bloodlines, as its the story of one vamp over a few centuries trying to get his girl back and stake the son of a ***** who screwed him over. I still think Bloodlines has an interesting plot to it though (plus a great ending)