Fahrenheit was ... Unbelievably good in the beginning, stunningly bad in the end. It was a great game nevertheless and I love it for the way it's story is told. +1 for you! :D

Indeed, I really like Fahrenheit most because of its story telling than its story itself. Meh, I played it until almost the end when I dropped it... and played the savegame two (yes two) years later because I was bored and wanted some free HDD space. I can't believe they screwed it so much x).

Good call with Crusader. I still play that game now and again.
The Marathon series and Myth: The Fallen Lords both have great stories.

Storytelling is the one aspect of a game that I value the highest. My all-time favourite is by far Planescape: Torment - which has already been mentioned several times in this thread (that makes me very happy). I also would like to add the Thief-series in here, because even if they are not games that exactly focus on story, the way its handled is still one of the most atmospheric and gripping ones out there. Secondly, I must say that Neverwinter Nights 2: Mask of the Betrayer has absolutely fantastic storytelling (while the original campaign is great, but not spectacular), and is easily included on a list of 'best stories ever told,' in my book. Lastly I would like to say that The Witcher is amazing. I started playing it a couple of weeks ago when I got my hands on the enhanced edition with some effort (for some reason, local stores don't stock it, and not even Amazon had it available - eBay came to my rescue instead), and I must say it hosts fantastic storytelling.
In any case, simply because I love making lists, here are my personal top games when it comes to this aspect (in alphabetical order):
• Baldur's Gate II: Shadows of Amn / Throne of Bhaal
• Chrono Trigger
• Eternal Darkness: Sanity's Requiem
• Fallout
• Final Fantasy IX
• Neverwinter Nights 2: Mask of the Betrayer
• Planescape: Torment
• Star Wars: Knights of the Old Republic II: The Sith Lords
• Thief: The Dark Project / Thief II: The Metal Age / Thief: Deadly Shadows
• The Witcher

I can't believe nobody mentioned the Lands of Lore: Throne of Chaos.
A few other games with good story are:
Ground Control 1 & 2
Spellforce 1 & 2

Okami - a bit dense at first, but otherwise a really good look at legends and Gods NOT from the usual Norse/Greek pantheon, or any Western sources at all, which have been done to death.
Darwinia - you control the inhabitants of a computer fighting against a virus, brought into the system by the deadly threat of spam email. Immediately drew me in.
World of Goo - very, very charming story about Goos and their adventures.

Lands of Lore is amongst my favourite games of all time, but in terms of storytelling I never thought it was particularly powerful. Where it excelled was in gameplay and presentation. The game world it showed was very intriguing, however.

Nobody said Betrayal at Krondor yet? Kind of disappointing, it was written by a novelist, after all. Ultima games also kept a decent narrative throughout. And then there's Albion, which had a "save the world" plot set up so good, by the time it was revealed, you actually cared.
Also, I liked how things were done in Unreal, but that's me (some people still claim that there was no story at all).

Anyplace to make my own text based adventure? I can't seem to figure out the coding (haven't tried) for one myself and I have some killer ideas..

Useful wikipedia article
However, note that most of the systems mentioned in the article (except ADRIFT, which seems easiest to pick up and use, if somewhat limited) are still programming languages, only dealing with plot itself rather than memory, display modes etc. :)

Actually, look into Inform 7. It uses actual English sentences to build interactive fiction.
As for games with good storytelling, I'm astounded that nobody's mentioned the Myst series yet. Those games had incredible storytelling.

My favourite 5 games with a good story:
Outcast
Omikron
Anachronox
Planescape: Torment
The Longest Journey

OMG, Kindo, you've shamed me. I have to commit hara-kiri now. How could I have left out the most awesome storytelling in the history of computer gaming? I'm turning in my gamer's card this instant [slinks off with his tail between his legs]...

I guess it's not cool on this site to pick a new game, but I think Mass Effect told a good story.

http://www.ifarchive.org/
I found as a place to start, but the site is deliciously text based itself :}
There are some tools out there that let you build them easily. I think there are a few on http://sourceforge.net/, but I can't say for sure.
The Wintermute Engine, while designed for Point'n'Click adventure games, is powerful enough to do text based adventures
An for those who have not seen this awesome piece of software, get yourself over to : http://dead-code.org/home/
Finally, there is the fun of having a go at programming. I made a very dodgy 5 room game, back in High School, using Turbo Pascal!
Couldn't figure out a proper word parser, but it taught me a little on how it all works. With all the resources around now, getting something basic as a proof of concept should be more easy.