Apple Store/play is not a new concept. It's a closed off, propriety version of a Linux or BSD package repo or ports tree.
All either company had to do was allow third party repositories. You get a nice list, choose which companies you trust, have a nice interface where you could download an app.repo file, view it's cert and add it to your phone. 90% of people wouldn't use it, but for power uses and beta testers, it would allow a single easy software update system that could be free for all. I wrote about this a while back in a post I did on OSS philosophy:
http://penguindreams.org/blog/the-philosophy-of-open-source-...