Hmm... I started with Mandrake (7 or 8?) and went to RedHat 9 back when Mandrake was in trouble, and released a few really crappy versions that didn't install at all.
RedHat 9 has proven to be quite stable and usable for me. Not as easy to finely configure, but then again, if you're just starting out, you probably don't want to jump into that much config at the very start.
RH9 seems to have fixed a lot of the dependency problems mentioned above. I've done some really strange stuff to mine, and it's kept its packages straight, even after a force or two, and a few installs from sources, etc. Also, a nice thing is that you can install apt-get on it, as well, thus giving you simple updates.
RH9 base is probably a little dated to start from by now, though. You should probably start with Fedora. I'm going to go to it pretty soon, myself.