The iOS App Store has problems that run deeper than the software customers use to access it. But if there are any easy wins to be had in the quest to improve the App Store, they lie in the user experience dictated by iOS itself.
The App Store has one goal: connect users with the software they need. That's what makes developers and Apple money, split 70/30. At times, the store has almost completely fallen down in achieving its mission. Remember the immediate post–Flappy Bird era, when a search for anything whatsoever — not just games — would guarantee a Flappy clone showing up in the top five results?
There haven't been any obvious leaps forward in search result quality, but there has been one major innovation in search interaction: the introduction of universal Siri search on tvOS. The new paradigm is drill-down search, where successive queries to Siri filter results. This model is well suited to TV and film media, where there is well-maintained metadata across several dimensions: genre, year, actors, and reliable reviews. But when App Store search came to tvOS 9.2, it was of the simpler kind, just by keyword. Perhaps that level of detail doesn't exist on the smaller tvOS store. It also doesn't exist on the gigantic iOS store, but Apple should be mining it for iOS 10 and beyond.
There's already plenty of underlying data that could create useful search combinations that are currently impossible on iOS. What if you could ask Siri, "Show me puzzle games. Only the good ones. Only ones without in-app purchases." Currently, at best you can find a puzzle subgenre or look for apps featured by app editorial or hope that a collection of pay-once games has been curated — and that it doesn't disappear. My guess is that the average iOS user doesn't search in the App Store because they don't get anything back from it. Either you know to ask for an app by name (and even that's no guarantee) or you're stuck window shopping in the featured tab.
This is why this problem is called "discoverability" — not just "discovery" — there is literally no interface to access many great apps. Keeping interface minimal, by using Siri, would be a smart choice (only power users love an advanced search UI). It would also make for great 30-second demos akin to the classic iPhone advertising that kicked off the "There's an app for that" revolution.
And with any luck, it would only be the beginning. It's another level beyond to ask "Show me scanner apps. Only ones with an OCR feature. And iCloud support." App descriptions and reviews would have to be parsed — what's a feature, whose opinion makes an app good? But opinions are better than nothing. Anything that can recapture the interest and trust of App Store customers would be a huge win for everyone involved.