An important feature of application packages is the separation of authority between the OS and the application. The installer needs to protect the system from the vendor. Most of the problems with Windows applications arise because the vendor-provided application installers have always been allowed to walk all over the operating system. RPM was a great leap forward, since the executable code was provided by the system and the package contained only information. Essentially, packages are interpreted by the RPM runtime. This leaves control in the hands of the root user, not the app provider. The Amiga installer was actually a lisp dialect interpreter! One could argue the the usefulness of the the Gentoo Portage system comes from layering a standard install api on code from varied sources and allowing the system to set common options across all installs easily. I'm sure Debian users would preach the joys of that system as well.
Dependencies are clearly a hard problem, especially with binary packages, since the unix idiom is that all options and dependencies need to be configured at compile-time. That problem really centers around code design, not packaging. The best that a packaging system can do is NOT MAKE IT WORSE. A good packaging system makes a system manageable by putting the authority in the hands of the operator. A weak or nonexistant packaging system leads to dll hell, packages breaking other packages and brittle, unstable systems.