I recently gave a talk at TEDxAmericanRiviera that touched on this subject: I think it is an enjoyable and understandable explanation of what it means that the ecosystem of software on the iPhone is limited to "applications", and how that is not what consumers want.
http://www.youtube.com/watch?v=ReKCp9K_Jqw
As some people may not wish to watch a video, I will go ahead and attempt to provide a little context here, in text. The idea is that the App Store is designed to install "applications": units of software that typically involve an icon on some kind of launcher that opens a window into some new functionality the device previously did not have.
However, is that really all that users want to be able to do with their devices? If we just look at the stories posted to Hacker News about Android software we already see that would be a flawed premise: there is a long train of "cool" surrounding products like Swype and 8pen. These programs replace the system input manager, aka the keyboard, for all applications.
These programs are not just apps: they are extensions to other applications on the device. We also see this in the form of custom launchers, dialers, and widgets: Android has numerous ways that developers can extend the core functionality of the handset in ways that escape the trap that is the icon.
Now, before you start thinking "woah, Android is awesome", you still can't add functionality to the address book, the notification area, or the task switcher... or any of the other insanely large number of things that the device is capable of doing. Every time you add a little bit more ability there is still going to be a ton of things that are not exposed.
You may now ask: what else is there? Go look at your average jailbroken iPhone: the stuff people are developing and installing is /amazing/. There are almost no limits to what you can change on the device; it isn't open source, but it is damned close. No system feature or application is immune to the influence of small and large changes. (For some cool examples and screenshots, watch the aforementioned talk.) And, if you really insist that open isn't open until it is open source you can gut the bootloader and install Android on the thing thanks to the iDroid project.
This is why I absolutely hate it when I read people focusing on rejected applications or "opening up" the app store. In a future where Apple did /exactly what you are asking them to do/ almost nothing will have changed: people will still need to jailbreak their phones and developers will still be writing and distributing all of this cool software using Cydia.
Seriously: Apple doesn't actually deny much from their App Store. They are occasionally a little anti-competitive, and that sucks, but these really boil down to a handful of high-profile cases: the effect on the market is minimal. Most of what they deny either a) doesn't work or b) is illegal or morally objectionable to your average American.
I say "American", as that's key: by having Apple, a US company, be the gatekeeper of content, there is a plethora of software involving aspects of copyright or slander law that is simply illegal for them to distribute. Meanwhile, things like pornography are a nigh-unto-no-go for their business model.
But please understand: that's the /only/ important issue with Apple being the shepherd, that is not an issue that your average iPhone jailbreaker or Android rooter (the classes of user that I think are central to this discussion as they are the poster child of a user affected by the closed policies of these companies enough to take matters into their own hand) gives a care in the world to.
Really, if you browse through Cydia, you will find only a small handful of applications. The number of applications that are in Cydia as "refugees" from the App Store was always low, and it is dwindling very rapidly as Apple slowly opens up their Store more (thanks to some nice efforts by companies like Adobe). Everything people jailbreak for is fundamentally not deployable by the App Store applications they /are not apps/.
So please... PLEASE... I /implore/ you: drop the battle to get Apple to open up their App Store(s). Instead, work on getting Apple to open up their /device/ (and, in the case of desktop Mac OS X, to maintain the reasonable open-ness of their MacBook line of computers). Until users are able to install whatever software they wish on the hardware that they own we will not truly have won back any of our freedom.