I hardly ever encounter a situation when the automated dependency resolution doesn't do what is supposed to do. The only problem could be that you do not need the same compile options that your distro has set for any given package therefore the dependencies you'd like are different from the ones you get.

If you really wanna be in control, use something ala gentoo or source-mage ;)

As for the topic, I'd give a try to stable linux distros like Red Hat(CentOS) or Opensuse :) (although they might not be really updated)

Regards

Everything MikeEnIke just recommended is Debian based, Debian is a great OS, Ubuntu is based off Debian, LinuxMint is based off Ubuntu from what I understand. I really think you would be happy with Ubuntu, if your worried about stability use their LTS version and you will be fine. Once you try Ubuntu and get used to it, and use the software center to find more useful apps for projects you run into you will fall in love with it.

I'm in the middle of upgrading to Ubuntu 11.10 right now. So grab yourself a cup of Ubuntu (11.10 Lastest and Greatest or 10.10 Long Term Support version). You will love either one.

I run both Scientific Linux (a Red Hat clone similar to CentOS) on my workstation, and Ubuntu on my laptop for the past 4 years without any desktop stability issues whatsoever. I wish I could say that Windows has been as reliable...