The dependency problem is a necessary artifact of software development. Developers take advantage of existing code libraries for common functions; it makes sense not to duplicate work that's already been done. They depend on the same libraries being on end users' target machines when their applications are compiled and linked there. If the libraries are missing, you can't build executable code.
One distribution, Debian, with its apt-get feature, seems to work quite well at fetching and installing code fragments it knows about. But apt-get depends on available packages being packaged into DEB binary files, and not all developers bother to create these. Apt-get also relies on a file on each client's machine that lists servers that hold available content. If you're looking for a relatively obscure library or package, even if it's available in DEB format, you may have to edit the list to help Debian find it.
Of course, you can install binary executables without building them, but these files often depend on the presence of external object libraries. However, binary packages such as Red Hat's RPM format don't work for every distro, and they don't always solve the dependency problem. You still have to resolve install dependencies manually before you install the RPM.
Another way to avoid dependency problems is to install only programs already packaged for your distro. But that limits your choices.
Guess who does it better?
I can think of one operating system that doesn't have a problem with dependencies -- Microsoft Windows. You typically never build Windows applications from source. Because a single company sets the standard code base, developers know that every Windows computer will have a certain set of libraries, which they can use with confidence. New versions of the operating system install new versions of the libraries, and the updates do sometimes break existing software -- a syndrome commonly known as "DLL hell" -- which goes to show how difficult it is for even a monolithic organization to solve this problem.
If only Linux had a single overarching authority that would demand, or even strongly suggest, that a certain set of libraries be installed by default with every distro. Of course that kind of authoritarian approach is anathema to today's open source community, where freedom is the compelling value even at the expense of ease of use. Will projects like the Linux Standards Base improve the situation. We'll see. Until the culture changes, I see little hope of resolving the problem of complicated software installation.
Absent a benevolent dictator's decree, perhaps the parties responsible for the distros would take it upon themselves to load up on development libraries. They could offer a minimal install for folks still trying to run Linux on 486 boxes and a normal install for the rest of us that includes as many common libraries as possible.
Even if that were to happen, it would be only a first step toward a solution. Utilities like urpmi, up2date, apt4rpm and OpenPKG may be a step in the right direction, especially if they become widely adopted. Until we have a universal tool for resolving application dependencies, we can't expect casual users to be able to install their own applications.