Go with Fedora if all you want is something easy to use, stable, and fast (enough). I just switched from XP Pro to Fedora Core 1 (I would have used FC2 but I heard there are a lot of bugs, plus I've had trouble with kernel 2.6.x in the past...) and I couldn't be more happier. I just installed everything, and within about 2 hours, I have everything working properly (NVIDIA 3D drivers, internet and routing for my laptop, samba, multimedia keyboard, FireFox, VNC, etc), and it's fast as hell (faster then the fresh install of XP that I had before).
Here's some distributions I've tried in the past on my system (the P4, specs in sig):
Slackware 9: Faster then fedora during boot-up, didn't really seem any faster during regular usage or during heavy CPU work (compiling, etc). I couldn't get a few devices working, but if I invested more time into it then I could have. If you have time, this would be the best distribution (except, no apt-get, which sold me on Fedora) it is very newbie friendly, but I just didn't have the time to get all the dependencies and programs I needed working correctly.
Mandrake 9.1: Slower then Fedora (for KDE usage), very bloated, got almost everything working (no NVIDIA 3D drivers or multimedia keyboard), but overall it seemed like Windows was a better choice then this (no offense, just my $0.02). Now, on my older computer (P3-500, 256MB PC100) Mandrake works great!
Debian Woody: VERY FAST AND VERY STABLE - I could not manage to crash X-windows! apt-get is definetly a plus, but, this requires quite a learning curve and isn't as newbie friendly as something like Fedora or Mandrake. I run this on my older laptop and it is around the same speed as Win98SE. There are almost no GUI configuration programs which made it hard for me.
Gentoo: I tried this, and halfway through the install I gave up - just took too much time. I'm sure if you have time this is an awesome distribution, and it seemed fast during the install, but too advanced for me.
That might give you some help to decide, but really, it comes down to personal preference. You might even to decide to do what I did (after my fedora partition ran out of space - 10GB with a full FC1 install lasted me about 3 days lol), which is wipe out my windows partition (30GB), install Fedora in it's place, then run VMWare Workstation and have XP inside that - works well for those occasional windows-only programs (I haven't run into anything that important yet though - Vmware hasnt seen any action).
I'll read up on it, but I guess like most noobs I want some multimedia, abiword, evolution, and a printer without too much of a headache.
Just give Fedora a shot (hell, you already have the discs burnt, what do you have to loose
), I think you will like what you see. I probably sound like a Fedora-fanboy, which I am, but you don't know how glad I am to finally be Windows free! I've been dual booting between Windows XP and different linux distributions ever since I built this computer and I finally found one that replaces windows! Good luck, and if you need any help feel free to ask, in all my tweaking I've picked up a few things!