Moi je ne connais que la Ubuntu. Elle est très facile à installer et ne m'as pour l'instant poser aucun probleme. Elle est basée sur une debian ce qui implique qu'elle beneficie de l'excellent apt pour la gestion des packages. Elle est mise à jour très regulierement et ils sortent une release tous les 6 mois. Le systeme de base est plutot leger. C'est "livré" avec gnome (ubuntu) ou KDE (kubuntu). Il y a des live-CD pour l'essayer.
Maintenant, la gentoo, pour ce que j'en ai entendu dire, c'est une tres bonne distrib' pour ceux qui veulent du "sur-mesure" mais visiblement, il faut y consacrer beaucoup de temps. En gros, tu dois tout compiler lors de l'installation ce qui te laisse le choix de prendre uniquement ce que tu veux.
Comme je n'ai pas le temps de me mettre sur une gentoo, j'ai préféré la Ubuntu. Elle allie la simplicité de mandrake avec la puissance de debian je trouve (je suiis passé par les deux).