Gnome. KDE sucks.
Personally, I don't know what Distro you should use. My favorites are Gentoo and Debian, because you can choose what you install and you have these things, like, you can issue a command so this stuff happens and the computer automatically fetches some source or binary files to install a certain program.
For example, in Debian, you open a terminal and enter:
Code:
apt-get install beep-media-player
This would install a very nice Winamp-clone (even better than XMMS). It fetches the files from a server and installs them really fast on your system. With Gentoo, it's kinda the same, but instead of binary stuff (precompiled stuff you just put on your system, just like in Windows), it fetches source and compiles it and optimizes it for your system. Basically, in Gentoo, you build your entire system from source very easily. Thus, everything on your system is optimized and, theoretically, blazin' fast. But compiling from source takes time. So, everything you install, basically takes a long time unless you're on a fast system.
I used Gentoo for months but I realized that this whole optimization stuff is really not that much, so I went for Debian eventually. Installing stuff on Debian is really fast. On Gentoo, it was like "fetching file... compiling.. zzzzzzzz... take minutes!" but on Debian it's more like "fetching file... SLAM!!!!!!". It slaps all that stuff right on your system, just like in Windows.
If you don't mind this cool stuff, than you should go for Fedora or something. It's basically like RedHat. No idea how they install programs though. You probably have to go manually to a website to get an .RPM file, and then you have to install it. And then you would have to worry about dependancies but maybe they fixed that or something.
Just make sure you go for GNU Object Model Environment a.k.a. GNOME, unless your system is kinda slow.