The burgeoning market for Android apps and the open nature of the Android platform and Market have already attracted upward of 30,000 apps. It doesn't matter that the iPhone apps store has 10 times as many; 30,000 apps is plenty, really -- enough that your biggest problem in locating a good app for a specific purpose might be winnowing out the also-rans and the not-quite-what-I-had-in-minds.
Tip 1: Use AppBrain.com from your PC or Mac
I like finding apps online, but not necessarily from my phone. I can type a lot better at my computer. And as nice as Web browsing can be on an Android phone, for some inexplicable reason it just isn't as nice as browsing from a quad-core PC with a fast graphics card that is hard-wired to a cable internet connection.
The official Google Android Market (see Tip 3) is all well and good when you are using your phone, but from your PC or Mac, the Android Market website only displays "some of the featured and top ranked applications and games available on Android Market." These "top ranked" applications are often fairly good, but without comments and ratings you miss out on some important details, and without a search function you can't easily home in on what you want.
There's another alternative for finding Android apps online from your computer: AppBrain. As it says in the AppBrain FAQ:
AppBrain is a website for discovering Android apps. In addition to providing search and browse functionality, users of Android phones can download the apps they chose by simply clicking an install button on the site. AppBrain then stores the application in an application wishlist. A companion native Android app then lets the user efficiently make all the desired changes on the phone.
The applications come from the Android Market; AppBrain just offers another interface to the market.
Tip 2: Look in the book "Best Android Apps"
While a book about something as fast-moving as the Android Market is doomed to a short shelf life, Mike Hendrickson and Brian Sawyer's book "Best Android Apps" offers a nice selection of 200 apps that is current as of April 2010. While I might quibble about whether some of their runners-ups might be superior to some of their top choices (or whether it really serves the public interest to select a best app for useless facts), overall Hendrickson and Sawyer have made some solid selections.
If an app in the book strikes your fancy, flip to the back of the book, find the QR code for the app by name, run Barcode Scanner on your phone, and frame the QR code in your camera. You'll have the app downloaded in no time. You can also use your phone to scan a QR code displayed on your computer screen to grab an app quickly after reading a favorable review online.
Tip 3: Search the Android Market from your phone
You can always search the Android Market directly from your phone. If you know the exact name of the app you want, this works very well. If you're searching or browsing, you may have to wade through a lot of crap to find what you want. Looking at the user ratings and the bracket for the number of downloads for apps helps -- up to a point.
One essential difference between the Android Market and the iPhone App Store has to do with curation. Apple gatekeepers have to actively approve an app before it appears in the App Store; the same goes for updates and bug fixes. Google employees who maintain the Android Market allow developers free rein to post apps, but quickly take down malicious apps. The statistics, ratings, and version histories of apps in the Android Market tell you a lot about how an app has been received by others.
Unfortunately, the Android Market ratings have been attracting incredible amounts of spam postings, usually with five-star ratings for the app whose comments they are spamming; in addition to being annoying, this screws up the averages. Take the average ratings with a big grain of salt and concentrate on what the serious comments have to say; when there are hardware/software problems reported, consider what handset the commenter was using. If you're using an Evo, you don't care if the app runs slowly on a G1 (a much slower device) or "force closes" (has an error that causes the Android to kill the running app) on an Droid (a device from a different manufacturer with a different CPU running a different OS version).
I like using the three sources I've discussed to find a bunch of apps in a category of interest. I then read their descriptions and comments, and download the interesting ones. I almost always start with free apps, even if I might eventually end up upgrading to the paid version after I've had experience with the free version. The processes of downloading, installing, updating, and deleting apps in Android are all relatively painless, especially compared to the BlackBerry equivalents; I don't mind downloading several similar apps, trying them out, and deleting the ones I don't like. My device (the HTC Incredible) has gobs of internal storage and a removable micro-SD card, so space is not a constraint.
By the way, you can take a look at what's on my phone. But understand that my list is constantly in flux; the fact that an app is on my phone only means that I'm trying it out, not that I like it or recommend it.