I've just come from Blackberry, here are a couple of my favs that I've downloaded:
"Mileage": This app is free - track and record you fuel mileage easily. Review statistics and trends. Great if you drive a lot and if you care about it...
"Jewels": an addictive copy of the game "bejeweled". Can't go wrong for free
"Paper Toss": just an easy, good looking game to kill a few minutes if you have to. Also free.
"Weatherbug Elite": Pay app - The most comprehensive, easy to use, best looking weather app I tried
"Widget Locker": Pay app - allows you to completely customize how the locking screen looks and works. Allows you to add widgets to it, shortcuts to apps, change the style of locking slider etc. Also allows you to set a different locking screen background vs. your desktop background. Note, depending how you set this up your phone won't be completely locked when it is locked, because you can still open and close apps, widgets etc.
"Convert Pad": A handy free app to quickly convert just about any unit you would ever need to during everyday life.
+1 vote for "Ringlert": awesome app for free ringtones, alert sounds etc. Much easier than searching the net, downloading, transferring to your phone... etc.
"Dialer One" A free dialer replacement using T9 and your contacts to find and dial contacts easily.
"Handscent SMS": A free SMS handler. Better looking and easy to manage than the stock messaging app.
"Where's my Droid?": A free app. set a codeword or phrase and if you can't find your phone get someone else to text it. you can set it to override the ring settings and ring loud for a set period of time, also turn on the gps via a different phrase or the same one. I frequently forget where I put my phone down in the house, and this has made it much easier / quicker to find it by sending a text from the wife's phone.
Those are some of the ones I use regularly.