I think I'm one of the minority that would not recommend Ubuntu if you really want a Linux experience.

For an amazing, free, and replaceable alternative to Windows then great, Ubuntu is perfect, but for me it's has lost all of original Linux vibe it once had, and when I use it I just don't get that Linux feel.

I'd start off Fedora, it offers the simplicity of Ubuntu, but allows for much greater configuration from the initial install, even though this may mean having to spending a little time before hand and after the installation reading up on certain things.

It puts a little more emphasis on using the command line, and from doing so you will learn alot.
If you wanted to, from then you could try out other, more configurable distributions that would really get your feet wet.

I've only been using Linux for about 6 years, and I've learnt much more in the last year and half since switching to Arch Linux than I had with any other distribution in the time before.

My journey was:
Gentoo > SuSe > PCLinuxOS > Ubuntu > Fedora > Arch Linux
I've found home with Arch, but I'm now venturing into BSD.