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 Android
Downloads a crowd-sourced advertising blacklist, redirecting in-app adverts to localhost.

Adobe Reader
PDFs at the beach: life is good! smile

Advanced Task Killer
Nuke leftover tasks to save battery, bandwidth, and reduce snooping.

Android Assistant
Swiss-Army-Knife grab bag of useful tools, most of which I've now replaced with better standalone ones.

Android Terminal Emulator
The dreaded command-line.

Barcode Scanner
Google Goggles
RedLaser Barcode & QR Scanner
Vivino Wine Scanner
Scan and identify just about anything, get in-store price comparisons etc.

Battery Indicator
Show battery level as a percentage, along with a notification tray item.

BusyBox Pro
More command-line stuff, but some apps rely on it too.

Call Control - Call Blocker
To reduce the carpet-cleaning calls to a dull roar.

Canada Topo Maps Pro
Free backcountry GPS navigation, world-wide (not just Canada).

Canadian Weather
Graphics and text straight from the Environment Canada website.

Crossword Solver
SWMBO does a lot of crosswords, and this helps keep me sane.

Data ON-OFF
A widget for those of us on finite data usage plans with exorbitant overage charges.

File Manager
The 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 Magazine
News and stories, beautifully presented.

Free Dictionary Org
A really good online/offline english dictionary.

GCC - GeoCache Calculator
A heck of a lot more than just "Geocache" calculations.

Mobi Calculator Free
RealCalc Scientific Calculator
More useful number crunchers.

GPS Status & Toolbox
Mandatory app: see the sensors on the phone do their tricks.

IMDb Movies & TV
Okay, not useful, but entertaining. smile

K-9 Mail
For non-Gmail email. The built-in email client sucks worse.

Lux Auto Brightness
Way, WAY better than the default "auto-brightness" app from Jelly Bean.

Ottawa Citizen
My local community news.

Permission Friendly Apps
Permissions Denied
Figure out which apps might be snooping, and put a stop to it without uninstalling useful things.

Smart Magnifier
Flashlight & magnifier card -- works well enough.

Smart Tools
More clever tools to measure things with the camera etc..

Smart Screen Off PRO
Automatically turns the screen off when in my pocket or face down on a table.

Smooth Calendar
Great calendar/reminder widget (not a full calendar app, just a widget).

Titanium Backup Pro * root
The 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 Radio
Internet Radio. Good app.

Voice Calendar
Really, really good voice-entry system for use with the Calendar app.

WiFi File Explorer PRO
Exports the droid's filesystems over Wifi for access from any other computer's web browser.

Wifi Analyzer
A really, REALLY cool Wifi access point detector and reception analyzer.

Wifi Toggle Widget
A simple touch widget to toggle wifi on/off -- other similar widgets available for bluetooth etc..

Wikipedia
My external memory. smile

ConnectBot
SSH client -- I'm actually running the latest development snapshot which is less buggy than the one at the Play store.

Blik Calendar Widget
A really cool Calendar manager with activity icons. Except it just hangs when I try it here. I want it though!

Openvpn for Android
If 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.