Got a lot of the apps already listed but thought i would throw in some i havent seen yet:
anycut - create custom shortcuts to any program, contact, text, action, ect and create your own title. (i like having handcent display as Messaging instead of Handcent SMS)
AndFTP - FTP client
atrackdog - manage your apps and will tell you when an update is available
appsinstaller - installs non market apps
better terminal - terminal emulator
bubble - a bubble level (if you remember the iphone commecial)
cragisphone - im a craigslist junkie
easy dial pro - i dont really use the dialer part but has a nice detailed call log
fxcamera - a camera w/ some cool filters/effects
handycalc - calc w/ way more features than stock
locale - best...app...ever! just get it.
liquor run mobile - closest liquor stores and closing times. cuz ya never know...
calwidget - a calander widget...duh
note me - a cool note/task list app
places directory - like yellow pages from google
swiftp - an ftp server, i use it to connect to the phone and xfer files over wireless
taskiller - a task killer
toddler lock - locks the phone and makes sounds and colors when the screen is pressed. i hand this to my daughter when we're in the store and it keeps her entertained the whole time.
Trapster - speed trap map
TuneWiki - media player that displays lyrics but also has integrated shoutcast and last.fm
wifiscanner - for scanning for networks
orb - not really an app but the streaming works great on our phones so i can listen to my home music collection from anywhere
on that note, the utorrent web interface works pretty well too. do a lot of torrent managing from my phone that way.
some of the more usefull ones ive found. i would like to see:
xm/sirius app
a good video player (ahem...coreplayer...)
wunderradio
a good Remote Desktop app (that doesnt costs $20)
and for the person looking for the MassSMS app, theres one called SMS Barrage here:
http://anda.pk/