I glanced at most of the comments and noticed a sort of pattern: a lot of you guys started (or at least remember to be first) with slackware.
short version: slackware ('98) => ubuntu 6 ('06) => gentoo ('07) => mac (boooooooooooooo, not linux, or is it?).
I started with Slackware 3.4 in 98 (I was 10 yo then) found on CD from a magazine (I don't remember the name, pcworld or smth).
Back then I owned this crappy cyrix 5x86 75mhz with 16mb ram and 240mb hdd. Very soon I upgraded to more modern hardware though (mmx and stuff).
I managed to get it to run and was so amazed how fast it is compared to windows 98. I used that piece of crap (the computer that is) until 2005 and learned php on a lamp stack (I remember using apache 1.2.22 until 2005, mysql 3.2 and then 4.4 or something like that, php 3 then php 4.3 as they became available).
I remember Slackware didn't make it easy to install packages. I had to hunt dependencies and manually install (compile actually) everything. Whatever didn't kiss I patched (tvtuner kernel modules were the worst :)) ). Never commited anything though because my patches were ugly and their purpose was to build on my system and nothing more.
In 2006 tried Ubuntu and loved aptitude. However in 2007 I met Gentoo at work and loved it even more because I could tweak everything compile related and have all the dependencies fetched, compiled and installed for me. I was in awe.
Sure I could have met Gentoo earlier, I could have used Fedora earlier and go all yum yum but all the experience I got using Slackware would be in an alternate universe.
What I can give is this: It doesn't matter what distro you start with. It matters A LOT if you really dig into it and try all you can to understand it's purpose. If it has a package manager, try not using it once and do everything by hand. This experiment will reveal so much about the distro and those similar to the one you're using you will not believe how well you understand everything after. Play with kernel parameters a lot. Break GRUB (or GRUB2) and fix it. Play with xorg.conf if you have the chance. You can't do this in one day, or one week. It will take a lot of time but eventually you will feel that whatever distro you're using everything is easy to understand, easy to use, easy to own.