I played around with several, so I may have some details wrong but IIRC it was:
RedHat 4 -> Slackware -> Debian Woody -> RedHat 7 -> Mandrake -> Ubuntu -> Debian Squeeze
Of these, the two Debian install were the ones that stayed on my computer the longest, and I've pretty much settled on it now. It is rock solid, doesn't randomly break stuff with updates and has a great package manager and repository.
The RPM hell related to the early libc changes put me off of RedHat for a long time. I decided that if I was going to futz with that sort of stuff I might as well use a simpler distro that exposed you to it, hence Slackware, which was a nice learning experience. I'd really like to do a Linux From Scratch install one of these days to update my understanding of modern Linux ecosystem internals.
I wasn't thrilled with Mandrake. I chose it because it was supposed to have nice hardware setup wizards, but when I ran them they silently failed, leaving me with no clue of what happened, and leaving the system config files in an inconsistent half configured state. I had to read through the scripts line by line to figure out what they had done and undo the damage (or wipe and reinstall).
Then I got tired of building my own machines and decided to support Dell's step into the Desktop Linux world. Hence Ubuntu. Out of the box it worked great. But every single upgrade after that broke something. Usually the Intel graphics, sometimes the audio. I eventually got fed up with it and went back to Debian.