Well here are my 2 cents ....
I personally use - besides Windows XP for gaming, some university related stuff - Debian (
www.debian.org) and LFS (
http://www.linuxfromscratch.org), tweaked to be almost fully 64-bit (with some necessary 32-bit libs). Most of my time I'm using the Debian distro as the LFS one was just for testing/learning purposes.
So someone recommended Ubuntu to you, I would second this recommendation because it's an easy to use distribution, which, as far as I know, was designed to suite the beginners needs.
The reason I would prefer Ubuntu to RedHat is that it is pretty close to Debian - and I always felt like Debian does NOT too heavily interfere with your "freedom" of tweaking the distro to YOUR needs. Many distributions somehow do too much for you - like for example that's the way I felt with SuSE in the beginning (maybe they improved over the years).
It's possible to do things "manually" with every linux distro BUT if you choose to use their config programs again, they will probably simply overwrite your changes in certain files. Just be careful once you decided to go a step further.
One or two words regarding Gentoo, I truely wouldn't suggest it as a beginners distribution. As Zeyus said, he thought about the learning effect Gentoo would have - but in my opinion it will just help you understand how to install a Gentoo distribution (doh!) and how things work with configuration files, etc. (which is a good thing after all). It's too Gentoo specific in itself that it is not teaching you what linux as such but what gentoo is all about. If you really want to learn something about what a distribution actually is, what is necessary to run a minimal linux environment, etc. I can only suggest you use LFS. LFS is not actually a distribution, it's simply a book on how to create your distribution followed by BLFS, etc. Once you have enough experience with Linux, LFS will help you delve a bit deeper - they have a pretty good way to explain things but you need to have a better (basic) picture of how linux works before you can actually make sense out of their explanations, instead of just following their instructions. Same applies IMHO to Gentoo.
This wasn't meant to "diss" Gentoo, but from my point of view, LFS gives you a purer Linux impression than Gentoo ever will.
To sum it up - it probably boils down to your personal taste. For me it's Debian, for WellyWu it's Redhat - for you it may be SuSE, Ubuntu, RedHat, etc. Just as with music there is no best distribution (as there is no wrong or right musical genre) - so take every opinion with a grain of salt (especially mine *g*).
I would suggest - besides the arguments given in this thread - you try a few distributions before you decide which one to keep on your harddrive. It all depends on what you need and what you expect from Linux - but rest assured, there are so many different distributions that I'm sure one of them will come close to your needs.
If I would have to begin with Linux today, I would use Ubuntu and if I feel the need to go a bit further I'd install Debian and would immediatly feel at home because I would know how things worked in Ubuntu.
Marcus