Go is awesome. I've only been playing for a few weeks, but I can easily see how it's the best game ever. It will take you 5 minutes to learn, and several lifetimes to master. All through the game you're making hard decisions, it's even more tense than something like Quake. I don't like the 13x13 board, only 19x19 or 9x9 if I don't have time for a full size game.

Learn the rules:
http://playgo.to/interactive/

Learn some basic tactics and strategy so you don't get totally owned:
http://senseis.xmp.net/?PagesForBeginners

Play online:
http://kgs.kiseido.com/

Improve your tactical skill:
http://www.goproblems.com/