This is a really old list, and people don't need help finding great Android apps anymore. I'm leaving this up for nostalgia's sake :-)
What I will keep up to date here are my smartphones: Moto Q, Motorola Backflip, HTC Aria, Samsung Galaxy Captivate, Samsung Captivate Glide, LG Thrill, Samsung Galaxy S2, LG Nitro, Samsung Galaxy S2 Skyrocket, HTC One X, LG e970 (basically a Nexus 4)
----------------------------------------------------------------
I used the Motorola Backflip in March 2010, the HTC Aria in late-June/early-July 2010 and the Samsung Galaxy S Captivate late-July through the present. My wife uses a Backflip, and my son uses a Captivate. Just kidding about my son (mostly). My next phone will be a Samsung Galaxy S 2, because it has a big beautiful screen, blazing processor, decent battery life, is moddable (CyanogenMod is my preference) with Samsung's explicit support, and because its Engadget review is just about the most glowing review I've read about anything.
A humble goal of mine is to one day contribute enhancements to Android or some other open source project which has enhanced my life.
Thanks to Mitch Katz for helping me get started with the best Android apps. All of the following apps are free, except SwiftKey and QuickOffice. I put the apps I'm not really sold on in parentheses. It is current as of early 2011.
(Adobe AIR)
(Adobe Flash Player)
Adobe Photoshop Express
Adobe Reader
ADW.Launcher - Just a better interface for your home screen. Very customizable.
Alarm Clock Plus - Better than stock alarm clock, I think. Maybe not.
AllShare
(Amazon MP3)
Amazon Mobile
AndDaaven - Works on Android 2.1 and below, despite those versions not supporting Hebrew. I assume they use jpegs.
Android Agenda Widget
Android Terminal Emulator - Show a terminal on your phone instead of having to use adb on the computer. Not for most users.
androidVNC
Angry Birds
AngryBirds Backup - Backup your Angry Birds state.
Angry Birds Rio
Angry Birds Seasons
Angry Birds Season Backup - Backup your Angry Birds Seasons state.
APNdroid - Critical if you want to use a smartphone but not buy a data plan (yes, it's possible to do, I've done it). Also helpful if you want to limit your data usage.
Astrid Tasks - Synchronizes with Google Tasks.
ASTRO File Manager - File browser.
Barcode Scanner - Kind of a must have. Gives ability to scan barcodes, including QR codes (which are becoming increasingly relevant).
Battery Widget - Show percentage battery left, which strangely is not native to Android.
(Best Parking)
(BlueKeyboard JP - Bluetooth stack)
Bluetooth File Transfer
Bookmarks to SD - Dolphin plugin for backing up and restoring bookmarks.
Books - Google Books.
Box - Like Dropbox, but 50GB free
CamScanner - Take pictures with your phone camera to turn into a PDF
Capital One Mobile Banking
Chumash Daily Portions
Compass
Craigslist - Execellent example of how an app can unleash the potential of a website
Daf Yomi - Probably not of interest to non-Jews. Study Gemara on your phone. Doesn't allow changing the Daf in the free version (extremely limiting).
DC Metro Transit Info - Next bus, train arrivals, favorite stops, favorite stations, etc. Very helpful.
DialerOne - Just a better interface for your dialer. Very customizable.
Documents To Go - Office suite most compatible with Microsoft Office standards.
Dolphin Browser HD - Best browser, in my opinion. Much better than the preinstalled browser.
Dolphin Screen Cut - Dolphin plugin which allows you to take a screen capture and edit/crop for saving or sharing.
Dolphin Tab History
Dolphin Tab Mix Plus - Dolphin plugin which supposedly mirrors the desktop Firefox version of TabMixPlus, which would be awesome. It doesn't seem to work for me, though.
Dolphin Translate
Dropbox - Ability to easily and seamlessly synchronize files between all devices (computers, laptops, phone, etc).
Duties of the Heart - Jewish book by Rabbi Moshe Chayim Luzzato.
eBuddy Messenger - Log into all your instant messaging/chat accounts in one app.
Engadget - A good example of when an app is better than a webpage.
(eHow Mobile)
ES File Explorer - Like ASTRO
Evernote
eSpeak for Android
Facebook for Android
Facebook Messenger
Fandango Movies - I prefer Flixter's app. Allows you to purchase tickets at some theaters which can't be done through Flixster.
Fidelity Investments - Allows remote check deposit
Fing - Network Tools
Flash Player
Fring - Cheap calls abroad
GasBuddy - Map and get details on the cheapest gas stations near you. Location aware.
GDocs
Gmail - If you want threading, labels, and all Gmail features, use this app for your Gmail.
Gmote 2.0 - Haven't used it, but seems to be able to control your computer/TV as a remote.
Google+
Google Books - eReader app, like Kindle and Nook eReader.
Google Chrome to Phone - Needs Chrome extension to be installed as well. Send links to your phone easily.
Google Currents
Google Docs
Google Goggles
Google Maps - Must have. Basically Google Maps, plus a free GPS that knows the traffic.
Google Music - My music player of choice. Note: Can be a data hog
Google Offers - Like Groupon, but should one day be able to play particularly nicely with NFC
Google Reader - RSS Reader, not as full-featured as NewsRob and doesn't seem to be very good with offline reading. Credentials are via Android API, which is arguably safer than how NewsRob does it.
Google Search
Google Shopper - Take a picture of an item (or barcode), and it will identify, price and give you options for purchasing it.
Google Translate - Translate text between languages. Autosenses input language. Includes voice input recognition and text-to-speech output.
Google Talk - Gchat, works like Instant Messenger.
Google Voice - Free texting. You can cancel your text plan if you use this. You just need to give people your Google Voice number instead of your cell number. Also cheap international calls, seamlessly integrated into your phone's dialing interface.
Groupon
Groupon National Deals - Aggregates all Groupon deals which can be used anywhere in the country (e.g. a deal for a website).
GScript Lite
GTasks - synchronizes with your Google Tasks.
IMDb
(Instant Lyrics Lite)
Jewels - Game modeled after Bejeweled.
Jewish Books Shmirat Halashon - Probably not of interest to non-Jews. Study Sefer Shmirat Halashon on your phone. Hebrew only.
Jewish Books Sefer HaHinuch - Probably not of interest to non-Jews. Study Sefer HaChinuch on your phone. Hebrew only.
Jewish Books Yalkut Shimoni - Probably not of interest to non-Jews. Study Sefer Yalkut Shimoni on your phone. Hebrew only.
Jewish Books Rambam - Probably not of interest to non-Jews. Study Rambam on your phone. Hebrew only.
Layar - Augmented reality browser.
Listen - Google podcasts, for lack of a better term.
(LivingSocial)
Llama - Location Profiles - Automate your phone. Very cool and helpful.
Meridian Media Player - Better music player than what's preinstalled.
Mobo Video Player Pro - Not sure which is better, Mobo or Meridian
Movies by Flixter - Easily watch all recent movie trailers. Find movie times and theaters.
Moviefone - I prefer Flixter's app.
Mozy - New entrant into the Dropbox-like space
(Multi Memo)
Music - Google Music.
Music Junk - Free music streaming and lyrics.
NewsRob - RSS reader. Synchronized with your Google Reader feeds. Very full-featured, perhaps the best out there.
Onavo | Monitor Data Usage - See which apps are using the network the most
Opera Mobile web browser - Another great browser. I prefer Dolphin, but many prefer Opera.
OS Monitor
Overlook Fing - Network security tool.
Pandora Internet Radio - Intelligent radio (plays songs it thinks you'll like based on how much you like the songs it's played thus far).
Paypal - Pay from your phone.
Peapod - Online grocery ordering.
Pee*Free - Find a restroom nearby.
Penetrate - Connect to certain wifi networks.
PowerAMP Music Player - Was highly recommended to me. Haven't used it, though. This is a free trial. Full version costs $5.
Price Check by Amazon
Priximity Wifi - Turns on wifi when you are near a wifi hotspot you've used before.
Pulse News
Qik Video - Free calls with anyone else who has Qik. Video calls too, depending on the phone.
QuickOffice
(Quick Settings)
RealCalc Scientific Calculator - Better calculator that what's preinstalled.
RemoteDroid - Use your Android phone to control and access your desktop. Requires an agent install on the desktop. Haven't used it yet.
Ringdroid - Create your own ringtone, including an easy to use music editor
ROM Manager - This is essential for most cases of modding your phone.
ROM Toolbox - Its free version is better featured in many respects than the free version of ROM Manager
Samsung Galaxy S Unlock Tool - SIM unlock your GSM Galaxy S
Schwab Mobile - Deposit checks remotely.
Sefira Reminders
Shazam - Play a song for Shazam, and it'll tell you the name and details of the song. I don't think you can sing to it, though I hear other apps can handle that.
Siddur Ashkenaz (Free edition)
Simple Calendar Widget - I like this better than the agenda widget above
Sipdroid voIP + video - Allows you to make free phone calls via data connection. No minutes used!
Skyfire - Web browser. Seems its claim to fame is its ability to play flash, so it may be less relevant once everyone gets Android 2.2+ (mostly the case already). I prefer Dolphin.
Skype
Solitaire - I used to be really into freecell. Like really into it. Got this in case I feel like starting that again.
Speedtest.net Mobile - Test your internet speed.
Startup Cleaner 2.0 - Get rid of any crap your carrier/manufacturer tries to load when the phone starts
Street View on Google Maps
StumbleUpon - I use it for its ability to "StumbleUpon" Android apps.
Superuser
SwiftKey X Keyboard - Up there with Swype as best keyboards. Predicts text based on what you've typed before, including grammatical and structural context. Very intelligent. Costs money now after the trial period ends.
Swype Keyboard - I don't think this is available in the Market, but there are ways of getting it. It is the best soft keyboard I've ever used.
Tab Mix Plus (Dolphin plugin)
TalkBack - Screen reader for Android application accessibility.
Task Manager - Ability to kill running tasks.
Tel3Dialer - App to make cheap international calls. I just use Google Voice now, but have this since I have some credit remaining from the days when I used it.
(The Coupons App)
The Weather Channel - Location aware.
Timeriffic - Free but more limited alternative to Locale. Make different things happen (e.g. toggle wifi or GPS) based on stimuli (e.g. time of day).
Titanium Backup for root - Allows you to make complete backups of your current setup in case you need to recover
Traffic Jam Free - Classic cars game where goal is to move your car from one end of the screen to the opening on the other side. Other cars impede your path, and you have to move them around to get your car out.
Trapball - Jezzball-like game.
TTS Service Extended - Text to speech.
TV.com - Watch full episodes of CBS shows.
Unblock Me FREE - Same as Traffic Jam Free, but this allows you to select your level more easily.
Viber : Free Calls & Messages
Vlingo Virtual Assistant - I use this because I'm on Android 2.1, which doesn't support Google Actions.
Voice Recorder
Voice Search
Volume Setting [cVolume] - Central place to control all your volume settings.
Vonage Mobile
Vz Wi-Fi Connect
wardrive - Map wifi hotspots if GPS is enabled.
Web to PDF - Dolphin plugin. Save a webpage as a PDF.
Wifi Analyzer - Detail the wifi around you.
Wifi Connecter Library - Used by Wiki Analyzer to connect to wifi hotspots.
Wifi Finder
WiFinder - Wifi connection manager.
XDA-Developers - Stay abreast of XDA forum updates.
(Yahoo! Music Radio)
YouTube
YouTube Ripper
Zmanim - Location based listing of today's Jewish times.