I would imagine a "normal customer" gets a direct referral to an application via a friend (someone who already went through the hell of searching), a television show, an review in a newspaper/magazine, or an ad on another website they are reading (or, these days, another app, quite possibly Facebook, Instagram, or Snapchat). At best, the only thing they are going to care about from Apple are, as you say, the extremey short curated lists (which are like the store front displays at a retail store, which you walk past on the way to your destination) and maybe the automated recommendations (which are supposed to be similar to the person helping you at the store making a suggestion based on having seen you before and knowing the kinds of things you like to buy, but in too many cases look more like the "impulse buy" section of a grocery store, showing you high-margin, general-audience items for which the entire rest of the store might be a "loss leader").
This is how "normal customers" bought video games when the primary distribution channel was "a massive wall of games at Toys R' Us, sorted by title", and this is how they still buy video games in the world of Steam (which people also complain is used as a dumping ground). This is how "normal customers" rent movies (only a cinephile is sifting through the mountain of low quality titles to find the diamond in the rough); and this is even how most "normal customers" watch movies at the cinema despite the relative lack of selection: in practice people go to a theater quite rarely, and so rely on trailers seen before previous movies (which are a combination of recommendations from the theater and the production company as well as paid placements), ads on television, reviews in the Entertainment section of their local newspaper, and referrals from friends... this is why independent films flop even when they get wide distribution, as they don't do much marketing.
This is how "normal customers" buy food, and I don't just mean at restaurants (where the closest thing people have to search is Yelp, which is comically bad for most use cases--it doesn't even understand the concept "bar is open, but kitchen is closed"--and maintains the same fiction that averaging five star ratings has any meaning at all): my friends think I am extremely weird for occasionally spending multiple hours at a grocery store "browsing" to discover the moral equivalents of "new releases" and "older titles I might have missed". In fact, the only other people I know who do this are foodies and cooks: "normal customers" know what they want to buy and minimize their time at the store, and at best are persuaded by a "related product" while putting an item into their shopping cart, an "impulse buy" at the point of checkout, or something at the endcap showcases that are effectively just curated lists; I'd bet TV commercials and coupons dominate.
App developers find this surprising only because they care so much about apps and are so sure their app is so much better than all the other apps that they are totally shocked other people are not appaphiles and that there are not better tools to find their app. The "normal customer", though, finds this no more surprising than how difficult it is to find literally anything else they want to buy, and the really successful companies either came with knowledge of or take the time to learn about marketing in order to reach the "normal customer" (which includes stuff like "how to make an app "viral", but also is a lot of classic "get the word out" effort). Expecting the Apple App Store, or any any-store, to solve discoverability problems is naive: if people really believe this they should take their expertise and go revolutionize retail (though in practice tons of people think they can do this, and then try to do this by building a low quality app, adding to the noise ;P).