IMO, the iPhone app store is probably the single biggest innovation of the iPhone...and it's not even a technological innovation so much as an assertion that things should be done the right way for a change. Here in the states as well as abroad, Apple used its power to strong arm their cellular partners into acting the way they should act - as an INFRASTRUCTURE provider.
Cellular companies have always been very short sighted about their role with respect to applications at the end point. They would push crappy applications (cellular companies don't know how to develop mobile applications!) to the device via tightly regulated network access and the result was a horrible customer experience. Thanks to the iPhone app store, those days are coming to and end. The fact that Verizon (historically one of the WORST culprits) here in the U.S. is allowing unfettered access to Android Market is indicative of this fact.
M