Craig Hockenberry makes a long list of recommendations for how to improve the App Store.
The two most important, I think, are the ability to do trials for applications, and upgrades. Trials because users will be much more likely to buy expensive applications when they can try them out first, and upgrades so developers can generate revenue from future significant updates.