Amazon.com has a free “paid” app every day. Many are fairly lame, but there are some pretty good ones as well - e.g. I got 3 different 15-dollar Office-emulation apps (Documents To Go, QuickOffice, OfficeSuite Pro), some decent games, etc.
A password vault. As much as I like 1Password (which we got when all we had was iPod Touches), that one isn’t useful for the Android, as it is readonly - you have to enter your passwords on a pricy desktop version, or on an Apple-based handheld. This hasn’t been a problem for me since I still use my iPod Touch.
Dropbox - seconded/thirded/whatevered. We have this running on both our phones (Android and iPhone) as well as both our laptops and our desktop computer.
DropSync - paid app, but works with DropBox to automatically back up files from different folders on the card. DropBox doesn’t automatically back up stuff from other locations, just its own folders, and I have a few apps that do their on-phone backup in specific directories.
A grocery shopping application which can also double as a todo-list manager. I’m using ToMarket because it’s the only one out there that does what I wanted: ability to have a single master list, and associate individual items to multiple stores. So you don’t have to have one list for Safeway, one for Giant etc., you can just check off everything you need and then filter by store (and sort by aisle for that specific store). All the others have separate lists per store.
Medication tracking: I really like Med Helper. It’s missing two features I had on the iPod (the ability to add comments to medication doses, and the ability to record vital signs) but otherwise it’s VERY useful if you take anything on a regular basis. There’s a free version and a paid version, I forget what the difference was but I went ahead and paid.
Sleep logging: Sleep Bot (free) - terrific tool. Much better than the best of the iPhone-based variants.
Widget Locker is good though if you’ve got a passcode on your phone (as you should), many of the widgets require you to put your passcode in anyway. Not all though - e.g. the flashlight, the sleep bot punch-in button.