People are releasing updates constantly just to get to the top of the list for new releases. Once you install apps you're constantly bombarded with updates that seemingly change or fix nothing. (because they don't, it's a marketing ploy) There's apparently no way to filter different languages out so I have to hunt through a list of apps with titles in languages. Apps have compatibility problems. The Market is littered with non-sense like "pre-CupCake edition" "Eclair edition" and "DOES NOT WORK WITH insert handset name here" Some apps just crash on startup. Some apps don't support virtual keyboards. I downloaded a random system monitor app that said every possible value like RAM/CPU was NULL. Compatibility is a problem. Some apps install services that cause other apps to work differently. For example I installed some random file manager that caused the photo app to take an extremely long time to startup. Removed it and all was well again.
There's no real easy way to UNINSTALL apps. You have to go to a list that includes everything including system components like com.something.blah.something. The Market doesn't support screenshots? or developers simply don't upload them? App naming is very inconsistent. One app might be AMAZING APP, another might be Amazing App, another might be Amazing App 1.0 Pre-Cupcake. Makes your program list a bit difficult to navigate. Apps can pollute your application list. I have something called UIServer-something or another in my programs list -- when I run it nothing happens. No clue what it is but it sounds important so I don't really want to remove it either.
So yeah... the grass isn't always greener. It's shaping up to be another Mac vs. PC thing where you can probably do more exotic things on the PC (Android in this case) but you pay a price for it with added complexity. The iPhone will offer a more seamless experience but you have to play by Apple's rules.
my guess is that once their library of apps is a bit more useful and full, they'll apply their search method to it. this will essentially give you the relevant apps when you look for something.