Ubuntu kör fortfarande Gnome, så vill du att det ska fungera bra och är enkelt skulle jag rekommendera Linux Mint eller Ubuntu.
Varför inte Fedora? jo p.g.a. att jag aldrig gillat rpm paketen och Fedora har värre dependencies än vad debian paketen någonsin haft.
Enda som kan strula lite är dock Ubuntu som fortfarande kör Gnome version 3.x något, fast med Unity och det sägs kunna strula och ställa till det en hel del.
Linux Mint använder dock äldre Gnome...2.x något tror jag och är något enklare och inte fullt så "flashigt" som nyare Gnome 3.x
Vill du köra KDE så är det Xuntu som du kanske ska titta lite närmare på.