I'd also advise against Ubuntu, it's a great OS, it really is, but imo it doesn't have that Linuxy feel anymore; it reminds me too much of Windows.

For a beginner I'd go for Fedora, and then move onto Arch Linux/Gentoo to understand the inner workings of Linux.