Ok you asked for it...
Look up software repositories in the Linux world. In general most distributions have been doing this for years now, in particular Debian based distributions. To install software and all of its dependencies is a matter of selecting it from the 'store' and telling the package manager to install it. That is it.
Likewise this has been adapted for, for pay, scenarios. To give an example look at the Ovi store assuming it ever gets off the ground, but you have companies like Sygic that distribute software for the n900 via a .deb format where they can just name to dependencies in the package, and it will install the software and the dependencies just as easy. Adding additional repositories is a piece of cake in that regards.
Now in as far as the app store idea for OS X, believe it or not, I am very much against it. The reason being is that in all cases where the Apple App Store is used now, Apple controls every aspect of what you can and cannot install easily on your machine. That would likely be one of the few things that would immediately make me walk away from OS X. It IS one of the reasons I don't care for the iPad or iPhone. But anything less restrictive and you pretty much have the repositories that Linux has been using for years.