The best thing that could happen to Android right now is for Google to unveil a real desktop client for the Android Market that provides a live view of the market as if viewed from a phone, filterable by hardware configuration and carrier. Ideally it would also be integrated with Google Checkout so that users could browse and purchase apps from their desktop.
As of this writing, this is what the official Android Market site looks like, and it's pretty horrible. It's just a landing page with a few outdated featured apps.
At one point Cyrket provided a live snapshot of the market, but Google did something on their end to make the feed that Cyrket was using unusable. So it's been dead for a while. And AndroidStats, a great site that used the Cyrket feed, is consequently also dead.
For a while people touted AndroidLib as a viable replacement. But it is horribly slow on my machine (I think it's probably not scaling well). It only filters by time and rating, and is far from from a live view. I also really dislike the interface, full of feeds and clutter.
So far the most viable 3rd-party contender is AndroidZoom. They had a makeover recently, and the site looks very good. Apps can be sorted by All/Free/Paid and Newest/Popularity/Rating. The interface is clean and sharp. The information is a bit outdated (this again is probably due to the lack of a live public feed), but it's probably the best thing out there right now.
At last estimate, the Android Market had over 20,000 apps and was still growing fast. Searching and browsing for apps only on your device is not ideal, and shouldn't be the only option. Google really needs to put together an official web portal, or at the very least make the public feed available again.