I'm going to go ahead and cast in another vote for Debian. It's much more advanced compared to Ubuntu (In my opinion.) Assuming you go about it in a minimalistic non-graphical install approach.

I think Debian is hard enough of a first linux distro to be learning everyday, yet forgiving enough to not make you hate it not to mention popular enough to find the answer to any question you should have from the installation, to configuration, to maintaining it.

Please feel free to send me a message (or jump on IRC) if you need any help at all, there is no such thing as stupid questions.