I would go with Ubuntu. It is a single CD which will get you up and running. It is pretty good at figuring out your configuration and getting all your hardware to work. You can then add on to it using Synaptic or apt-get to download programs from the Internet. It is based on the Debian distribution and it can run any of the Debian packages. Debian is a HUGE distribution with lots of support so there is almost nothing you can't run!
Once you get the desktop running look into a program called Synaptic Package Manager under your system->administration menu. It is a graphical front end for apt-get. Apt-get is sort of like Windows Update, but not only are there updates, there are thousands of other programs. Synaptic lets you browse them like a catalog. Pick what you want to install and it downloads and installs if for you.
For all the cool multimedia stuff someone has written a configurator called Automatix. Do a search for it on Google. It is sort of a blunt force install-all-this-cool-crap program. It has a nice list of things you will want to try out or use and saves you the time you would spend trying to find all these packages in the apt-get archives. It will give you video players, mp3 players, fonts, plug ins for Mozilla Fire fox...etc. It is a nice way to discover what is available. Way cool.
Most video plays better on Linux than Windows. Rather then needing a player for MPG/AVI, Quicktime for .MOV, and real player for .rm and .ram you can play them all on Mplayer. Just need to make sure you istall all the codecs.
Do a search for some Linux screen shots. The beauty of them is inspiring.
I started off with Redhat. Problem with a Redhat distro is that everything from the open standard has been tweaked by RedHat to the point that a lot of things just don't work right. I saw all these cool desktops, but those same apps didn't seem to run right under Redhat. The other caution I have against Redhat is with every release of FedoraCore it seems the availablity of packages for it gets slower and slower. Yum is slow and terrible. It is a really poor attempt to imitate apt-get. With Ubuntu stuff just works.
The other cool thing about Ubuntu is you can download a live CD version of it and try it out. In other words boot off of a CD into a working Linux desktop without touching your systems hard drive. Once you convinced it will work you can then go get the install CD and install it to your hard drive.