Pues ya depende del tiempo que quieras echar en la instalacion y del grado de optimización que quieras para tu distro.
Debian es una distribución orientada a procesadores 386 o superior, todo está compilado con esa base.
Gentoo se compila en la instalacion, para tu procesador específicamente, logicamente irá mas rapido a la hora de ejecutar cualquier cosa.
Las dos tienen sistema para instalar software, una apt-get y otra portage, en ese aspecto creo que estan al mismo nivel. (no entro en disputas de cual es mejor, me refiero a disponibilidad de paquetes)
Si estas empezando y no te quieres complicar mucho la vida, instalate Mandrake, si tienes ganas de aprender, cualquiera de las dos (gentoo y debian) es buena.
Saludos.