A friend who just got an Android phone asked me what Apps I use. Here's an edited version of what I wrote back.

The phone comes with an adequate set of apps to start, but you'll want to download many more using the built-in Market app. Of the built in apps, unsurprisingly I use phone, contacts and text the most followed by Camera+Gallery. Oh, and the Alarm Clock (get to it from any sensible Clock app).; it wakes me up even when there's a power failure, which happens a few times a year out where I live.
The built-in Google Maps is your basic GPS. OSMAnd from the Market is the same idea but using Open StreetMap data. The built-in GMAIL app, or the slightly better K9 mailer, to read mail on the go.
Angry Birds is a high-end time sink, er, game. "Memory" is simpler time sink. Tons of other games, about 15 or 20 Sudoku variants.
All of the eBook readers have Android versions: Kobo for one has tons of books from Project Gutenberg for free download (something useful to do on those interminable subway rides).
Aloqa finds restaurants, coffee, shops, etc. near you, using the GPS or Phone Tower nav.
Androidify lets you make your own silly Android avatar.
Barcode Scanner (the one from zxing) lets you scan the QR codes that you see everywhere; they mostly contain URLs that open in the browser. It will also scan the barcode from eg., a can of soup and find that for you on the web.
Google Googles will take pictures of everyday things and (try to) identify them.
Everybody's got a News app these days; take your pick of CBC News, BBC News, CNN, Fox News, etc. news apps.
CamCard will scan somebody's business card and load it into your Contacts. You give them back the card and say "Thank you, I have it memorized". Get the or version, it's better than the free version.
CIA Fact Book has a quaint GUI but still useful. WikiDroid is a front end to WikiPedia (connected, doesn't pre-load the whole DB though it could be made to fit now that they support apps on the SDCard.
OI Safe keeps track of your passwords, encrypted. OI File Manager (and others) let you explore the device; works like a File Manager ("Explorer") on a desktop.
SL4A (Scripting Layer for Android) lets you write python, shell, and other scripts that deal with your phone (dial out, etc.).
WeatherEye for weather forecasts.
Xabber for SMPP chat, if you use that. There might be a version of Pidgin now, for all I know.
Connectbot is a decent SSH client.
There are literally tens of thousands of other apps; these are the main add-on ones that I have found time to look at and use. Language learning. Games. Spreadsheets. All this you find in the Market app; just hit the Search icon once in Market and type what you want. Have fun. Use lots of data.