Mira si es para comenzar yo te recomiendo mandrake, pero la 10.0 (que todavia se llamaba mandrake) de la edicion especial que han sacado ahora con el nombre de mandriva si no he escuchado buenos comentarios, al parecer tiene muchos bugs flotando por ahi.
Ahora, debian no lo recomiendo no porque no sea bueno, sino porque el user base no es muy amigable (lamento herir sentimientos), pero al menos es la impresion que he tenido con la mayoria de usuarios debian que me ha tocado conocer... Ahora, si eres medio hardcore y quieres aprender por las malas, instalate slackware, stable, seguro actualizado y esta especialmente disenado para que lo modifiques vos a tu manera.. Y si en realidad queres aprenderte hasta el ultimo detalle de como funciona una distro linux te recomiend te armes tu distro personalizada con LFS (Linux From Scratch) el cual es una distribucion de linux basica que no trae mas que un Howto y las fuentes para compilarla (no la comparen con gentoo por favor), armar tu LFS se siente como comprar un juego de legos y comenzar a armarlo con las instrucciones, buenisimo en realidad ahi es donde aprendi la mayoria de como funcionan las distribuciones.
Si no quieres estar con dolores de cabeza te digo que instales Mandrake, tiene una infinidad de programas asi que no vas a tener que estar descargando, casi todo se configura solito y en general trabaja de una manera aceptable.