I've been an Android user for over a year now. I kind of agree. Most of this isn't gaming specific though. Here's the problems as I see it.
The search functionality in the android market stinks. This is Google "king of search", but if you don't have the exact app name, good luck finding anything.
There's only 1 level deep categorization. Big hierarchies are a pain to manage, and some apps fit multiple categories. And it's hard to display a tree on a small screen. But only having 1 level deep makes it very hard to browse. If you don't know the name of the app, have a QR code, the app isn't a top 20, or if it's not updated almost constantly, it's almost impossible to find.
A desktop client for browsing, searching, purchasing, and installing apps, and perhaps other content (movies, music) would be helpful. Basically iTunes for android. DoubleTwist addresses some of this, but the market integration is in it's infancy (and I don't know that purchasing will ever work, unless google buys doubleTwist - hey, there's an idea!)
Not having any kind of review process in the market, there's a lot of shovelware, and a lot of ip infringing crapware. There's even been some malware. It's kind of like the wild wild west. Or the internet. Sometimes, being an "open" system isn't such a good thing from a user perspective.
Outside of the market, I think that divergent hardware is an achilles heel, not a strength. There's what, 3 or 4 iphone versions to deal with? Android runs on what, dozens of models (or will). With so many phones with varying capabilities, and os versions - not to mention bugs and quirks like the nexus one multi-touch swapping, some applications, especially games that like to get as close to the hardware as possible are going to be difficult to make portable.