It's best to get a distro that can handle dependancies and installing programs in a intellegent manner. This is one of the downfalls of Mandrake, unfortunately. (the other one is that they depend to much on non-free stuff)
Suse has Yast, which seems to do a ok job.
The best is Debian and apt-get, by far. Although the distro itself is made to be generic as possible so that it's not the easiest thing to setup and get going for a lot of people. Ubuntu is based on Debian and so has a lot of the positive traits to it's package handling and software aviability, however unlike Debian they have a default desktop-oriented setup that includes what they think would be best for a common desktop enviroment (a modified Gnome setup, mostly). So that makes it a bit easier to handle and get used to.
Fedora core 3 has choice between Yum and a ported version of Apt-get that works with RPM files (debian has it's own package format: deb). It has everything you NEED to get going, but to find everything I want I find that I have to use third party packages from places like FreshRPMs and Dag Wieer's rpms. (do a search for dag rpm). I use their apt-get rpm package and it sets up everything neatly and quickly.
However Fedora Core 3 is more for the "enthusiests" type and users generally are the types that are willing to fill out bug reports and stuff time to time in order to have new stuff.
Now Mandrake has urpmi, which seems to work. I tried it out once, but it was a while ago so hopefully it has improved and quality of packages have improved. I didn't realy like it. I was mostly easier to do rpm searches for stuff.
Usually it takes a few tries to find a distro that suits you. Some people realy realy like Mandrake.. I don't personally. My favorite is Debian, but other people can't stand it. Some people love Gentoo, I think it's a bit of a waste of time, but it's ok IMO. I'd rather use the latest Fedora Core if I want to play around with newest stuff.
And there are lots more, like Xandros. Xandros is based on Debian it has apt-get, but it also claims that you can install RPMs easily as well. I don't know if that works out all that well, I'd rather just compile from source code then muck around with mixing packages from different distros.
The thing about installing software in Linux vs Windows is that there is a much different mentality because your dealing with free and open source software.
In Windows when you install a program the installer makes sure that you install everything you need to run along with the program.
In Linux those RPM files only include the actual program, they may need more packages installed to get the thing to actually run.
These "extras" are called "dependancies". When you get stuck with a program and having to install and muck around with different versions of packages and breaking applications by upgrading and downgrading to get a certain program to work and you end up searching all over the web to find certain packages from some guy and it ends up being a buggy package and it installs over some other stuff by accident, that is called "dependancy hell".
Similar to ".dll hell" in Windows.
A good package manager is able to avoid this, and makes life easier for the user. Although the biggest and most important factor is the quality of packages your using in the first place. You can have a very good pacakge manager, but if your using crappy packages or a crappy repository you end up with a huge mess on your hands. This is one of the reasons people like me like debian so much. They do a great job.
I suggest getting Ubuntu and Debian next time and see how that works out. Also Fedora Core 3 + Dag Wieers is very nice and has special bonuses like SELinux standard.
Synaptic package manager is a nice GUI front end for Apt-get that is aviable on most distros. Check that out. I prefer aptitude though. There are virtual packages for Debian that makes it easy to install big stuff that requires lots of packages, Like KDE or Gnome desktop enviroments...