After having used: Debian, Gentoo, Redhat, Fedora, Mandrake, Slackware, DamnSmall, Ubuntu, Libranet, BBC, Knoppix, Kubuntu, SuSe, and a few other randoms throughout the past few years...
I use Ubuntu on my laptops, Fedora on the desktops, and FreeBSD/Fedora on the production machines. (FreeBSD being on the "frontline" machines - with Fedora on the "backup" machines).
If you are "starting" - I would recommend either Fedora or Ubuntu just for the ease of use- but PLEASE - set up a dual-boot configuration - because there're some things you will still want to use your windows for - and it's a shame to wipe out Linux just to "go back" to Windows.
If you actually want to learn and set up a machine that'll run forever amen - take the time to learn Gentoo or FreeBSD and use those. Feel free to IM w/ any additional questions.