Von den Distributionen, die ich ausprobiert habe, gefiel mir RedHat9 ziemlich gut, aber das wurde ja dann zum RedHat Enterprise und statt Fedora habe ich dann Gentoo genommen. Bei meinem Rechner forderte das viel Geduld, weil das ständige kompilieren doch relativ lange dauerte. Für Einsteiger würde ich Gentoo nicht empfehlen, weil man (bei Stage1 Installation) ziemlich viel von Hand machen muss. Dadurch kann man aber auch sein System mal so richtig kennenlernen. Etwas Erfahrung davor wäre trotzdem nützlich, damit man nicht verzweifelt.
Jetzt nutze ich SimplyMepis 2004, eine Debian-basierte Distribution, die man von CD booten kann und dann auf Wunsch auch installieren kann. Danach gibts auch keine Probleme mit apt-get. Download zum Beispiel hier.
Bei mir funktioniert alles von selbst, sogar die nvidia-Grafiktreiber zu installieren war hier ein Kinderspiel (ein Häkchen bei "Offizieller NVIDIA-Treiber" und fertig).
Ich glaube am Besten ist immer noch ausprobieren und dann das nehmen, was einen persönlich am Meisten anspricht.
Tut mir leid wenn das etwas wirr klingt, ich bin noch nicht ganz nüchtern (die Ferien haben begonnen ;)).