I should have mentioned this before but if your a new linux user and have already gotten your hands wet in it, stay away from BSD for a while. Be look at it once you get comfortable with Linux though.
Fedora and Suse are going have easy installs, Ive heard linspire (what ever it is...used to be Lindows) is quite easy too. Fedora takes a lot of configuring to get good performance because its bloated. On the other hand your not going to find any better hardware detection. Check out yum if you go with Fedora. Havent tried Suse or Linspire.
My favorate... Slackware is pretty easy to install and is great for learning learning linux. Its also pretty stripped down so performance will be pretty good without modification. Be sure to check out swaret if you go with slackware. Also SLAX
is a live slackware version under 210Mb if you want to see it from a user stand point.
Debian seems to be one of the more popular distro's. I havent looked at it much but the install was quite difficult compared to any of the previous distro's Ive mentioned.
I still havent tried Gentoo cause I havent been able to get any of my spare boxes running yet. It sounds like it rules. Pretty much it compiles everything from source so performance will be great. emerge sounds like it kicks apt-get, yum, and swaret in the face, configures your packages, compiles them, and is ready to do some more kicking (yea thats good).
Just look around at different distro's and see what they have to offer...they are all Linux! Go with one you like.
Check out some of the live CD's if they are offered. Some of the better known live cd's are.
Knoppix - debian based
slax - slackware based
I believe slackware may have an official live cd now...not possitive.
A nice list can be found here: