OS Monitor for finding the pesky apps that are waking themselves up and running the background. Boat Browser is an example. I had never launched it before but it was starting itself up for whatever reason. Get off my phone!
GrooVeIP use your google voice phone number over data. With a fast 3g connection or Wifi the latency is great and sounds much better than using standard minutes.
A Online Radio for streaming free musics. I usually use this for SomaFM streaming GrooveSalad channel (chillout/ambient electronica).
ScoutMob for finding restaurants near you with hot deals (usually 50% off).
QuickPic lightweight replacement for Gallery App. Much faster to load and scroll through and find photos.
Wifi Analyzer to see the channels that wifi near you are on, so that you can set your router on a channel that's less "full".
FTPServer to create a server on android on wifi, then you can load files off your phone from your computer without plugging it in, very very nice.
GTasks has a great widgit.
OldMarket to bring back the Old Market style before they started trying to cram books and TV episodes and what have you down your throat.
Titanium backup a must if you like to root your phone and switch roms all the time like I do. It's also great for freezing or uninstalling apps which you're not using that wake themselves in the background, like the Gallery app and the Email app. I uninstalled both of those since I only use Gmail.
LauncherPro replacement launcher program, DEFINITELY the fastest launcher App there is out there IMHO, has the smoothest scrolling, love it. Lets you create shortcuts to direct activities, for example composing a new SMS with the stock SMS app and composing a new email in Gmail, I have both as their own shortcuts, just tap (or hotkeyed to the hardware keyboard shortcuts) and it opens a new email/sms. Probably one of my favorites for it makes using the phone just like blackberries of old with their keyboard shortcuts to compose email / sms / etc.