One person recommended Red Hat, another Fedora.  Both are top
choices.  They are very similar, with each version of Fedora kind of 
being the next version of Red Hat.  Fedora is free, and has the most up 
to date stuff.  After some particular software version has been used 
in Fedora for a while and any kinks are worked out, it then goes into 
Red Hat, which is more stable and reliable because it doesn't have 
the hottest new stuff.
I mentioned that Fedora is free.  It's not just free in terms of price, 
but free in terms of freedom.  It doesn't include any proprietary software 
or stuff with restrictive licenses.  We Linux geeks talk use the terms 
"free as in free beer" and "free as in free speech".  More on that in a moment.
We use Fedora and a version of RedHat called CentOS on our servers, 
desktops, and laptops, as well as other devices like my DVR.
I'm a little surprised that people say Ubuntu is easy for the newcomer.
I didn't think it was easier than Fedora, not at all.  to each their own, 
though.  One thing that makes Ubuntu a little easier is that it includes 
some non-free multimedia stuff which has to be separately installed 
in Fedora, 
but installing those multimedia codecs and RealPlayer only takes a few minutes.
Here's one guide, of many.  This may not be the best guide, as I've 
never gone through it's steps.  It's just the first one I found on Google:  
http://slayachronicles.blogspot.com/...in-centos.html
 
I should explain the relationship between CentOS and Red Hat (RHEL).
Red Hat is a commercial company and Red Hat is their trademarked brand.
When you buy Red Hat Enterprise Linux, you get not just the software, 
but a brief printed user manual and most importantly some support.
RH also points out that you get a professionally pressed CD.
The software itself is free as in free speech, so if you wanted to you 
could remove all of Red Hat's logos and sell it or give it away as 
"TommyM Linux".  That's what CentOS is - the exact same software 
as RHEL, with the Red Hat logos removed.  It's given away free.
That means it doesn't include support from Red hat Inc., you use free support - read HOWTOs on the web, read forums, etc.
BTW, the word "HOWTO" is magical in Linux.  That's the word you put 
in Google to find instructions to do just about anything - 
Linux networking HOWTO, Linux video card HOWTO, etc.
If you have any questions and can't find the answers via Google, 
feel free to contact us.  We've been using and administering Linux 
systems for over a decade.  If you have trouble finding the answers 
you seek, particularly if the experts don't seem to want to talk to you, 
read this little gem:
http://www.bettercgi.com/gpl/smart-questions.html
It's written by a famous Linux developer.  I've emailed him and he, like
most of the top experts in Linux, is more than happy to help IF you 
follow the suggestions in that HOWTO.
One other tip.  If you have a slower internet connection, downloading 
Linux could take a while.  If you have that problem, go to a large 
bookstore and look at the Linux magazines.  Often they will include 
a free Linux install disk in the magazine.  Also many books will 
include a Linux disk, but you have to make sure it's current.
Fedora releases a new version about every six months, so a two 
year old book won't have an up to date disk.
For any readers wondering WHY Linux is a great idea, I'm going 
to make a follow up post quoting a post I made the other day in 
response to a different question.