Actually Useful Stuff
reddit is fun is the unofficial official reddit app. Some people don't like it, a lot of people do. Check it out, but you can always still look at Reddit on your browser. Alternatively, Digg has an official Android app now too. I don't have it, so I don't know if it works, but you know... just FYI.
Locale (as described by some website): "This smart app uses GPS, WiFi, and cell signal to adjust your phone settings based on where you are, and when. It will automatically turn itself off in meetings and movies, remind you to charge the phone when battery runs low, and more. There’s no better way to have your phone take care of itself."
Urbanspoon is awesome for finding nearby restaurants depending on your mood, price, and location.
Movies by Flixter is handy if you go see a lot of movies. It lets you know what's playing nearby, what's opening, and what it has on the Tomatometer.
Barcode scanner does what it says. I use it to scan QR codes I find online, like this one for 10001 Cocktails, that automatically download apps to my phone.
Cab4Me shows you the locations of nearby cab companies and ratings, prices, and phone numbers.
If you're a traveler, TripIt has a fantastic itinerary app.
Shopsavvy is cool because it lets you scan barcodes on items at any store, and it shows you a map of all the places nearby that have that item and how much they sell it for. I haven't really gotten a chance to use it yet, but a lot of people like it.
I love A World of Photo. It's not very useful, but it's crazy interesting. Basically, someone on Earth "picks" you to take a photo of something around you, and you send it to them. Then, you point your phone in a direction and "pick" someone else, who has to send you a photo. See some cool ones here, at the World of Photo subreddit. You can rate the photos and send a comment to the sender without giving your phone number or any other info away, except for the World of Photo username you create. I've carried on conversations with all kinds of different people in different parts of the world about the photo they just took of their dog. I've also met redditors. You can make a short bio and people can look; most redditors mention reddit in their bio. I've gotten all kinds of awesome pictures, like a beach in Spain, and a guy in Germany(?) that was at a soccer (football lol) game. I got an actual photo of that game as it was occuring across the pond! It's really rad. I just take pictures of my cat with my ferret on his head.
Meebo IM lets you sign onto AIM, MSN, Yahoo, and ICQ all at the same time on your phone. If you've ever used http://meebo.com, you're already familiar with this app.
Twitter just released their official app, if you're into that, and Facebook comes standard on it (I'm sure you've noticed that by now). I'd used the default Twitter app, called Peep, and I've also used Seesmic and Tridroid, but I think I like the official app best. The Incredible also has "Friendstream" by default, which merges your friends' Facebook, Twitter, and Flickr updates into one thing, but I prefer having those items separate.
Tip Calc is a handy, easy-to-use Tip Calculator.
If you care, The Weather Channel has an official app. I don't care. But you might.
Ringdroid is awesome. You can take any song you have saved and cut out a part you'd like to use for a ringtone and save it. Beats paying for tones (or having to use myxer.com).
Pure Music is a better way to listen to music on your phone. It displays a widget on one of your pages that gives you full control to play, pause, or do whatever with your music without having to have your music app open, taking up your whole page.
Shazam identifies music for you. Like if you hear a song in a restaurant and you don't know what it is but you'd like to hear it later, just open Shazam and let it listen; it'll almost always correctly ID the song for you.
Grooveshark lets you stream music to your phone. There are other services like Pandora that will do this, too. Personal preference.
TuneWiki is rad. While you play music from your phone, it displays the lyrics, scrolling on your screen accordingly. The lyrics I've seen thus far have always been accurate and punctuated correctly, all the words are spelled right, etc. I believe you can use it for both music you have saved on your phone or Micro SD andstreaming music. I think.
Generally Useless Stuff
Pokedroid. A Pokedex for your phone. If you like Pokemon. You can actually speak the Pokemon's name into your phone and it pops up with its stats, the moves it can learn, when it evolves, and it even provides a link to its entry on Bulbapedia... I am a loser
If you like when people hate you, the Instant Button app is really helpful. It's basically The Instants Collection, but on your phone. Great. (Yes, I do have it, and yes, I do love it.) The great thing about most of the soundboards you can get is that you have the option of saving any of those sounds as notification sounds or ringtones. But I probably shouldn't have mentioned that.
Handcent SMS lets you completely customize your SMS experience, from colors to the way you are notified. You can have it use one of three different kinds of pop-ups when you get a message, or no popup at all. You can even change the little icon that appears in your notification bar when you get a message. It also lets you save pictures that people send you right to your Micro SD card. After getting Handcent, I recommend opening your "Messages" app that comes default on the phone, hitting the Menu button, and turning off notifications on that one so you're not notified on both Handcent and Messaging.
There are all kinds of different wallpaper apps you can get, which are basically huge collections of wallpapers you can choose from and set. I use 4chan Wallpapers because, well, 4chan is good at awesome wallpapers. I think there's a catch, though; you have to have that app either installed or running to use the wallpapers they provide. What I just do is pick a wallpaper, email (or SMS) it to myself, open that email on my phone and save the image to my SD card. That way, if I get rid of that app, I still have the wallpaper.
[List derived from Reddit User Helloeien's Comment]