Hola Rever
Antes de Mandriva existia Mandrake, yo empezé con Mandrake y en esos tiempos era muy bueno, por desgracia se ha convertido en un sistema muy comercial, lleva Compiz Fusion incorporado, la version Live de esa distro esta muy bien. Mandriva es bueno pero digo lo de siempre. Depende de para qué quieras el sistema, si lo qiueres para hacerte un "linuxero", no empiezes por Mandriva, empieza por Ubuntu, Gentoo o Debian, en cambio, si quieres meterte a Linux solo para huir de Windows pues entonces sí, ponte Mandriva o Fedora, que son sistemas muy amigables y faciles de usar.
Editado: Se me olvidaba, KDE es un entorno de escritorio, al igual que Gnome, es cuestion de gustos, no hay ni mejor ni peor, yo te recomiendo KDE, es muy util, y si qiueres lo puedes personalizar bastante desde kde-look.org. Y Compiz Fusion es un conjunto de plugins que crean diversos efectos en el escritorio, la gran mayoria de ellos son inutiles, pero hay otros utiles. Busca videos en youtube sobre Compiz Fusion si quieres, seguro que te gusta.
El tema de como se te lo bajas, pues depende de la distro que uses. Compiz Fusion viene incorporado en Mandriva, y KDE me parece que tamien lo lleva incorporado, no estoy seguro, de todas aneras eso no es un grave problema, Madriva seguramente lleve un gestor de paquetes desde el que te puedas bajar e instalar KDE.