Because the people that care about design don't really care about the App Store (they care about products instead), and the people that run the App Store don't really have an incentive to try and make dramatic changes in something that, from their perspective, is wildly successful. Change might break things, especially when operating on the scale that Apple is (just think of what the load must be on the App Store).

Apple executive leadership is responsible for successful change in all departments, they could make this a priority if they wanted.

That's true. And if you care about this issue, you could try appealing to Apple executive leadership (emailing tim cook, or running a PR campaign designed to get Apple executive leadership to see your arguments).

Alternately, one could invest in startups that solve this problem.

I don't know how much has come from it yet, but here's some an example of some investment:

"Apple Acquired Search Startup Ottocat To Power The ‘Explore’ Tab In The App Store"

http://techcrunch.com/2015/04/06/ottocat-apple/