Por que não os 2? Abre via Live CD (sem instalar) mesmo... dai você testa ambos.
Mas a principal diferença entre o KDE e o Gnome é:
Gnome: A filosofia é esconder recursos avançados (afinal usuários avançados conseguem localizar) e exibir de forma transparente o que todo mundo usa.
KDE: Exibe tudo e ponto. Pode parecer meio bagunçado, mas é mais flexível em alguns pontos.
Também tem que ver que existem programas pra KDE e programas pra Gnome. Claro que os do KDE rodam no Gnome e vice versa, mas não se encaixam bem nos temas e perdem um pouco a performance. Veja alguns programas que usam eles:
Gnome: Bluefish, Firefox, GIMP, Inkscape, Xara Xtreme, Gmplayer, Totem, Listen, Xchat, aMule, Evolution, F-spot, Gaim.
KDE: Konqueror, Opera, Kopete, amaroK, Ktoon, Scribus, Quanta, K3B, Koffice, Kmail.
Então se pra você tanto faz, opte pelo que tem a maior quantidade de programas que vc usa. Minha recomendação.
Eu por exemplo adoro Gnome, afinal eu uso simplismente TODOS os programas listados ali no Gnome. E dos do KDE só uso o Scribus e eventualmente ainda. Por outro lado tem gente que não vive sem K3B, amaroK e Opera.
Abraços!