Okay, now that Android handsets seem to be achieving World Domination, the quality of the Apps is also improving. Here are most of the ones I've discovered/installed for my own use thus far:
AdFree AndroidDownloads a crowd-sourced advertising blacklist, redirecting in-app adverts to localhost.
Adobe ReaderPDFs at the beach: life is good!
Advanced Task KillerNuke leftover tasks to save battery, bandwidth, and reduce snooping.
Android AssistantSwiss-Army-Knife grab bag of useful tools, most of which I've now replaced with better standalone ones.
Android Terminal EmulatorThe dreaded command-line.
Barcode ScannerGoogle GogglesRedLaser Barcode & QR ScannerVivino Wine ScannerScan and identify just about anything, get in-store price comparisons etc.
Battery IndicatorShow battery level as a percentage, along with a notification tray item.
BusyBox ProMore command-line stuff, but some apps rely on it too.
Call Control - Call BlockerTo reduce the carpet-cleaning calls to a dull roar.
Canada Topo Maps ProFree backcountry GPS navigation, world-wide (not just Canada).
Canadian WeatherGraphics and text straight from the Environment Canada website.
Crossword SolverSWMBO does a lot of crosswords, and this helps keep me sane.
Data ON-OFFA widget for those of us on finite data usage plans with exorbitant overage charges.
File ManagerThe current BEST file explorer/manager app (I've tried many others).
Can even browse/transfer files over wifi to/from Samba servers.
Flipboard: Your News MagazineNews and stories, beautifully presented.
Free Dictionary OrgA really good online/offline english dictionary.
GCC - GeoCache CalculatorA heck of a lot more than just "Geocache" calculations.
Mobi Calculator FreeRealCalc Scientific CalculatorMore useful number crunchers.
GPS Status & ToolboxMandatory app: see the sensors on the phone do their tricks.
IMDb Movies & TVOkay, not useful, but entertaining.
K-9 MailFor non-Gmail email. The built-in email client sucks worse.
Lux Auto BrightnessWay, WAY better than the default "auto-brightness" app from Jelly Bean.
Ottawa CitizenMy local community news.
Permission Friendly AppsPermissions DeniedFigure out which apps might be snooping, and put a stop to it without uninstalling useful things.
Smart MagnifierFlashlight & magnifier card -- works well enough.
Smart ToolsMore clever tools to measure things with the camera etc..
Smart Screen Off PROAutomatically turns the screen off when in my pocket or face down on a table.
Smooth CalendarGreat calendar/reminder widget (not a full calendar app, just a widget).
Titanium Backup Pro * rootThe gol^H^H^Htitanium standard for backups. I back things up locally within the Galaxy Nexus,
and then copy the backup off over Wifi to my server.
TuneIn RadioInternet Radio. Good app.
Voice CalendarReally, really good voice-entry system for use with the Calendar app.
WiFi File Explorer PROExports the droid's filesystems over Wifi for access from any other computer's web browser.
Wifi AnalyzerA really, REALLY cool Wifi access point detector and reception analyzer.
Wifi Toggle WidgetA simple touch widget to toggle wifi on/off -- other similar widgets available for bluetooth etc..
WikipediaMy external memory.
ConnectBotSSH client -- I'm actually running the latest development snapshot which is less buggy than the one at the Play store.
Blik Calendar WidgetA really cool Calendar manager with activity icons. Except it just hangs when I try it here. I want it though!
Openvpn for AndroidIf you need to use OpenVPN, then this is the modern way to do it on Android 4.x, rather than the old way that required rooting the phone.
I've also tried about twice as many other apps, and uninstalled them afterwards again. Didn't keep good enough records to list them here though.