Como dice quelcom puedes instalar debian con un cd (el primero) pero si tienes intencion de hacer la instalacion desde internet, si no necesitaras los 7. Si esta es tu opcion y no quieres bajar muchos mb puedes conseguir un mini cd de debian que te trae lo basico y el resto lo baja todo de internet.
Sobre lo que dicen de esta distro de la instalacion te aseguro que no es nada del otro mundo instalarla. Si lo he conseguido yo cualquiera lo hace
. La mayor complicacion que puedes tener es la configuracion de las X y aun asi es bastante sencillo. De todas formas si tienes un poco de paciencia espera a que salga la Sarge oficial que segun tengo entendido te facilita mucho las cosas.
Otra opcion de debian seria instalar ESware. Esta basada en debian y la instalacion y configuracion es muuuuy sencilla.
Sobre Gentoo... pues aparentemente si te "estudias" el handbook no es muy dificil de instalar (con ver los comandos te vale) aunque es mucho tiempo de instalacion, y si te da algun fallo despues de estar compilando hora y pico el x.org te puedes morir (lo digo por experiencia, que alfinal desesperare por instalarlas xD)
Esas son las dos opciones si tu nivel es suficiente. Si tus conocimientos son bajos te recomiendo que pruebes Suse, que en los ultimos tiempos ha subido mucho como distribucion. Ademas, el apt le puedes instalar.
Saludos!