Hola:
Bueno, la diferencia basica creo que estaba en el planteamiento, gnome intenta hacer un escritorio "asequible" a un usuario sin mucha idea y kde intenta hacer un escritorio mas potente (esto es una opinion, no es que me haya informado mucho). Pero en el fondo esto no supone ni una ventaja ni una desventaja para elegir uno o otro.
Creo que el kde es un poco mas lento (solo lo notaras con todas las chorradillas activadas y en equipos antiguos) pero es quiza mas "bonito" (tiene mas animaciones, transparencias, etc).
En cambio en el gnome todo esta un poco mas integrado, o eso me ha parecido, las aplicaciones se parecen mas entre ellas, y es mas simple de utilizar.
Si lo que quieres es decantarte por uno o por otro te va a tocar probarlos, yo al principio era fan de kde y no me gustaba gnome y ahora es un poco al reves, el aspecto inicial del kde es bastante parecido al de windows (la situacion del boton de inicio, las barras de tareas, los menus, etc) mientras que el de gnome no.
A mi por ejemplo el sistema de ventanas que mas me ha gustado de momento es uno que se llama xfce (esta en los repositorios de ubuntu pero no se si lleva todas las librerias y aplicaciones que si pones sus propios repositorios), es de lo mas simple que puedas encontrar (no monta usbs, las asociaciones las tienes que poner tu indicandole el comando a utilizar, etc), es mucho mas rapido y bastante bonito sin tener que buscar entre las opciones, pero al ser tan simple le faltan cosas que si tienen gnome y kde.
De todas maneras antes si que era mas problematica la eleccion de escritorio, porque no se podian utilizar las aplicaciones de uno en el otro, pero ahora si que se puede hacer.
Imagino que no he despejado demasiadas dudas, pero es que hay que probarlos, yo empeze con kde porque mandrake por defecto ponia ese y al final estoy usando gnome porque es el que viene con ubuntu tambien (xfce esta bien, pero no me entere que ubuntu automontaba los usb hasta que un dia me meti en el gnome para probar una cosa).
Saludos
PD: Perdon por la parrafada