LastPass - passable LastPass app. It's ugly, slow and a little frustrating to use, but better than having nothing at all…
Latitude Shortcuts - you're no longer able to launch Google Latitude directly from your apps list (it's part of Google Maps); this app restores that ability, which is invaluable for those of us frequently wanting to know where our friends are ;)
LinkedIn - LinkedIn app for those of us who use it
MemoWidget - lets you add a simple textual memo to your home screen
MyTracks - Google app to track your movements over a journey (e.g. walking, cycling, driving, etc.), then report back statistics and a plotted route
OkCupid - mobile app for OkCupid. Their developers need to take a read of the Android UI guidelines sometime, but mostly it's a nice enough app
Photo Editor - a very functional photo editor app. On older versions of Android it can't allocate enough memory to work with larger images (Android 2.3 combined with 12 megapixel images failed), but later Android versions are fine
Pocket (aka ReadItLater) - save articles to your Pocket in order to have it download them for offline reading as well as keeping a handy list of things that you need to read at some point
Popcorn Hour Remote - network-based remote control for Syabas Popcorn Hour media devices
ROM Manager - useful ROM management utility for rooted devices (REQUIRES ROOT)
Samba Filesharing - sets up a Samba server on your device in order to share your SD card over the network (REQUIRES ROOT)
SpeedTest.net - mobile version of the speedtest.net service; useful for testing your 3G speeds
SugarSync - client for people who use SugarSync's syncing/backup service
TED Videos - watch TED talk videos all neatly compiled into one place
Tesco - Tesco's app does various things, and no longer requires the overreaching “see list of running apps” permission!
TitaniumBackup - excellent (if confusing) backup utility that's invaluable if you flash new ROMs onto your device (REQUIRES ROOT - I think)
Watchdog Lite - keeps an eye on the CPU usage of apps and will alert you when an app starts using too much CPU (which Facebook has a habit of doing, totally out of the blue)
3G Watchdog - keeps track of 3G data usage, with a nice widget and such (had more utility before Android had similar functionality built-in, but the widget is still nice)
Caffeine - keeps the screen on and/or set to don't-dim-on-idle when connected to a power source (e.g. a desk/car dock)
DeskSMS - allows sending/reading of SMS messages through a Web interface (or via TabletSMS on an Android tablet; see below). NOTE: Still seems to have a bug where sent messages longer than 512 characters are cut off. Keep messages short-ish!
SMS Popup - displays incoming SMS messages in a pop-up dialog with options to quick-reply, read the message aloud using TTS, etc., and can be configured to have different notifications for each contact
Xbox Live Smartglass - Smartglass is Microsoft's new Xbox companion tech. Primarily I use it to let my phone act as a remote control for my Xbox, which is especially useful for entering text, where I get to use my phone's onscreen keyboard instead of the Xbox's
Tablet-Only Apps
Dolphin for Pad - a tablet version of Dolphin browser. Unfortunately it's very buggy, crashes frequently, and often switches tabs for no obvious reason
Tablet CPU Usage Monitor - monitors CPU usage of tablets, placing icons in the notification bar displaying CPU/RAM usage
TabletSMS - the Android tablet client for DeskSMS to allow sending SMS messages from your Android tablet via your Android phone (thus using my Asus Transformer's hardware keyboard to type messages)