I think you give Google too much credit. The Play store is about as abysmal, sans the OS-tied updates. (Search, lists, SEO, etc. are BAD).
I worked at Etsy for a number of years which has many similar attributes as the App Store, and lots of slow, steady progress was made by running many experiments and aggressively maintaining performance. I'd be licking my chops at the low hanging fruit if I were the one tasked with starting to hill-climb the App Store UX. There are so many things you could try, and with the type of traffic the App Store gets, 1% experiments could almost certainly get you sufficient data to really drive up conversion rates without negatively impacting many users along the way.
Meanwhile, the Play Store search and navigation used to suck, but they've both improved a lot, and they keep the highlighted content fresh and relevant, which surprises me coming from Google (though not having used an iOS device extensively I don't know how often they update their featured content, but from this post it sounds like not often enough). They've fixed most of the stupid issues they had before and I actually like using it now.
All the navigation is counter-intuitive (What do you mean swiping to the left doesn't go back and instead takes me to categories or who knows where? Why doesn't the back button take me back to my search results? etc). The curated front screen rarely seems to have anything new and interesting on it (for apps anyway, I never look at the media part of it), whereas the App Store constantly has new featured apps which are actually good. The first six months I had my Nexus 7 the "here's stuff you might like for your tablet" section didn't change.
I quite like my Nexus 7 and am considering switching to Android for my next phone now that I've found a few apps that I can bear using (and some of them are actually well designed to boot), but apart from automatic updating, the Play Store is not one of the attractions.
The swiping thing was referring to the category pop-out in the main sections (Apps etc) which makes it feel like it should do something else. In retrospect I probably should have waited until I had gotten home and double checked whether what I remembered was correct before commenting. Having a flip through it, the store is less awful than it was last time I paid it any serious attention - having a decent stable of usable apps I haven't had much cause to go looking for new stuff lately.
<terms> site:play.google.com (or, earlier, site:market.android.com)
as opposed to using the store's own search interface. Now I only do that when I'm looking for something the store will filter out (wrong device type, wrong country, etc.). I suspect the web search is still a bit better, but closing to the point where it is usually not worth the hassle is still a big step.
That being said, I'm surprised this has been such an issue, for either store. I'd have thought making sure your search results are better than a blind web search would be a standard thing to look at.
It needs to be much faster. It needs to be more engaging. The search needs to be improved. The taxonomy needs a massive overhaul. Users need to be more encouraged to review apps and the review process itself needs to be overhauled. App sellers need to be able to perform legit SEO on their keywords and get insights into where their downloads are coming from. Even buying an app feels sluggish and unresponsive. The recommendation system is crap because they recommend similar apps not complementary apps. The whole thing is just begging to be rebuilt, it's basically the same as when it first launched.
It's a huge optimization problem and it's absolutely embarrassing they are not constantly A/B testing, iterating, and improving the experience. It feels like they have no data science team at all working on this product. The fact that the App Store only changes with iOS updates shows they are approaching this product incorrectly. They should have dozens of experiments running all the time trying to drive up install rates. It's probably the biggest example I can think of where Apple really shows that they are unquestionably not Google.
It's hard to underestimate just how much of a boost Apple will see if they actually build a real, first-class, fast shopping experience into the App Store.