Yo elegiria Debian y como ya usaste Ubuntu alguna vez pues tienes algo de experiencia con paqueteria DEB, porque Debian por es estable, robusta y el respaldo de una buena comunidad tras ella.
Fedora no es mala opcion, todo se trata de cuestion de gustos, otra buena opcion Open Suse.
La instalacion completa de Debian es 6 discos, pero vasta con el primero, con paqueteria incluida, solo empapate de los repositorios que quieras añadirle, para luego descargar mas software si te hiciera falta.
No olvides que al momento de instalar el cargador de arranque, este debe estar en la primera parte del disco duro, es decir en reemplazo del cargador de arranque de windows, asi el GRUB o LILO tomara este lugar, dandote la posibilidad de elegir el sistema que quieras usar.
DebianFedoraopenSUSESaludos.