Aver, recomendar entre KDE y gnome es como recomendar una distribución, cada uno preferirà uno... ahora bien, debes tener en cuenta que como has dicho, esos dos son Escritorios, vienen con todo (calculadora, navegador, ofimatica...) pero a parte tienes los gestores de ventanas que simplemente son eso, gestionar el entorno de ventanas (WindowsMaker, ICEwm, fluxbox....)
Si tu salto va a ser desde windows, supongo que es recomendable usar KDE que se parece bastante a mi parecer, gnome, tira quizas mas a lo que son los mac, aunque los 2 son realmente configurables en cuanto a barras de tareas, etc etc...
Siempre puedes instalar los 2, y en principio mandrake te pediria siempre con la sesión que vas a iniciar, que gestor quieres usar (kde, gnome, icewm....) asi que podras probar, siempre que no tengas problemas de espacio, claro...
Recomiendo igual que como una disto, prueba las 2 y quedate la que mejor te vaya...