Then again, it's hardly a hard problem
Eh, I'd expect app discovery to be reasonably hard when you have a few hundred thousand developers and marketers incentivised to do anything they can to game the system.Here is an image of what looks like a worker in China manipulating App store rankings using an array of some hundred 5Cs.
http://i.imgur.com/EWyVh0X.jpg
And here is an image purportedly showing the prices for a Top 10 spot in Apple's App Store, achieved through ranking manipulation.
http://i.imgur.com/TZuf1iP.jpg
[1] This disturbing image of a Chinese worker with close to 100 iPhones reveals how App Store rankings can be manipulated
http://www.businessinsider.com/photo-shows-how-fake-app-stor...
Back when we used to sell stuff via operator (carriers) portals people would still use tricks like starting game names with the letter A to appear at the top of the lists, so attempts to game any system are not a new phenomenon.
Ultimately you have to play the game you find yourself in.
As a user, compared to Google Play, the iTunes App Store really sucks. Besides the discoverability issue, the Apple's store isn't even showing me reviews because Apple is limiting those reviews to reviews of locals only and in my country there aren't that many iPhone users that would be interested in the apps that I am interested in or that care to contribute reviews. And basically I end up installing junk in the hope that it's any good, or do searches on Google for recommendations - oh, the irony.
In any shop I go to, there are endless equivalent products to choose from.
The one I end up buying depends on price, marketing, visibility in media, word of mouth and so on.
Selling stuff is hard.
Then again, it's hardly a hard problem - it's just one that Apple has done almost nothing significant about over the years. Practically any solution is better for developers (and users) than the current status quo.