verizon's problem will be phone models
Apple's app store is easy, both for developers and for consumers. 95%+ apps work with all iPhones and iPod Touch's. Only a few are specific to either the iPod Touch or the iPhone, and there are might be some that are for only specific iPhone models. And end-users can easily (free for the iPhone, $10 for iPod Touch) upgrade to the latest OS, and get patches for free, so right now, the majority of iPhone owners and a good batch of iPod Touches are using the latest version of the OS. And then the App Store is relatively easy to purchase (less so to find) apps.
For everybody else, there are a bunch of hurdles blocking them from effectively competing with the app store:
-developers don't have a consistent platform to program against. Phones running different OS's need custom versions of apps, and then different model phones have different capabilities such as cpu, ram, screen, buttons, and even available API's.
-the firmware on most phones (except notably Android and Palm Pre phones) are rarely, if ever, upgraded. Unless there is a widely publicized problem or virus affecting a phone model, the OS just isn't updated, even with bug fixes. So developers either need to spend more time making sure their apps working with the install base, which uses older less capable API's OR code to newer API's, but then it works with little or no install base.
-the end user/store/developer all have to figure out how to make sure the app they purchase in the store actually will work with their particular phone (so you need to filter all the apps in the store based on manufacturer, specific model of phone, and the installed OS on the phone). So even existing stores offering thousands of apps, only a fraction of them will actually work with your specific phone