1: If search is how you access the huge variety of apps, why is the search bar hidden all the way in the top corner? When you open the app store on an iPad, you have a beautiful, but ultimately very limited view of apps.
There really needs to be, and I believe there is room in the market for, a service that helps discover new and upcoming apps. Both Apple and Google do a poor job helping users find apps they might like.
2: "Genius" is useless if you have to find apps you like first. It may help provide limited exposure to apps similar to ones you've tried, but it provides poor results if you don't know what you want in the first place.
3: Each of the categories provides only the "top XX" or "newest XX" apps. This incentivizes a cutthroat market and disincentives large investment into apps. Sure, there is a ton of VC money to chase many different app ideas, but ultimately, successful apps will need to make a return on investment. Both Apple and Google do no favors to developers by fueling the "turnover" game. You get one shot on the "new releases" board, then you're on your own for marketing outside of the app stores. In the long term, this will decrease the quality of apps on both platforms. Amazon has a shot at getting it right, and I believe this strategy may favor them in the long-term.
If you really want to win, find a way to improve discovery or "browsing" of apps. The market will follow the incentives to their logical ends, and right now, both of the big players are missing the opportunity to incentivize discovery of quality.
Nick
P.S. I don't know the solution to these problems either, but look for yourself and tell me they don't exist.