That's a lot of questions, but first step could be
http://distrowatch.com/. Read reviews, packages included in the distro etc.
Latest stable KDE (
http://www.kde.org/) is more stable and faster than before. Xfce (
http://www.xfce.org/), after two years of development have a new stable version 4.8. It's simple and fast. GNOME has released GNOME 3 (
http://gnome3.org/) and that's a new direction for it. A lot different than GNOME 2.
Few distros that I would recommend to you to check out, based on what you said are;
- http://linuxmint.com/
- http://www.mepis.org/
- http://www.xubuntu.org/
As far as I know Fedora is the only distro at the moment, released with GNOME 3 as default desktop environment. It also have spins with newest KDE and Xfce environments. It's a bleeding edge distro, after all.