You must be pretty frustrated with all these choices you have now. I've had experience with a good few mentioned, so let me break down the pros and cons for you...
Mandrake: Easy configuration, but paying money for packages is definitely not fun. Put a X through this one, my friend.
Fedora: Fair configuration tools, but it is a bit difficult to get superior multimedia support (because it is illegal). If you are going to watch DVDs, you may not be able to turn on DMA and your movies may be choppy. Recommended for business deployments on the cheap and servers.
Ubuntu: FREE CDs!!! [/url]http://shipit.ubuntu.com Not recommended for laptops because of not-so-hot networking configuration tool, but it has great multimedia support and decent configuration tools. Recommended for desktops. Also recommended if you are completely new to Linux: [url=http://help.ubuntu.com/starterguide/C/faqguide-all.html]http://help.ubuntu.com/starterguide/C/faqguide-all.html
SUSE: Great configuration tools, online update downloads are genuine patches instead of the entire thing, takes a bit of patience to get everything to work, especially on laptops.
As you can see, all three have their own advantages. I highly recommend Ubuntu or SUSE.
Once you finish installing, don't forget to learn about repositories as those are the things that will help you add the functionality you need.