Hi MHG,
I chose to install KDE on Debian, and I'm happy with it. I've seen people argue somewhat passionately (and unconvincingly) about the superiority of one over the other. Just my opinion, but I think it's a matter of personal preference, and you should take a look at both and see which one feels right to you.
You might try a couple of live cd's that come with one or the other as the default desktop to see which you like, before installing one to your hdd Linux install.
Knoppix has KDE as the default. I recommend Knoppix version 3.8.2 -- it worked better for me than 3.8.1 or 3.9.
Ubuntu live-cd comes with Gnome, so you might want to take a look at it for comparison. Of course, you'll have to factor in the difference between the two distros.
Good luck, and enjoy!