If I'm understanding your question, You can have both KDE and Gnome when installing Red Hat 9. If you have the drive space for it, I've found the best way to install first time is to install everything. The RH 9 install will give you that option. Fedora, Mandrake, Redhat 9, and many modern distros have a pretty straight forward graphical installation, which to me, is easier than a Windows install. I wouldn't reccommend trying to install Debian if this is your first attempt. It's a text based install and not easy. I've tried to install Debian 5 times and finally gave up!
Even with a graphical install, it may take 2 or three tries until you get your system set up the way you want it. Be sure to create a seperate partition for /home, so you can save your valuable files and preferences there from install to install.