I love the Android Market, hours of fun.
Apps:
SMS Popup - Self explanatory
WorldTour - Background image of a webcam/globe daylight (hard to explain but brilliant)
Locale - sets rules/actions depending on situations ie location, battery level etc.
TasKiller - Easy task manager/shutting down of apps.
MyTracks - GPS sports tracker
Beebplayer - iplayer for Android. (Plus Live TV/Radio)
Youtube - great app
Battery Graph - Shows you your battery usage, pretty important considering the power the syncing can use up.
Palringo - IM client (MSN, Skype, Gmail etc)
ChompSMS
Skype - You know
Twitroid - Twitter client
Hullomail - Visual/Email voicemail (Saves your voicemails as mp3's, emails them to you/saves to your phone.
Shazam - Song IDer
Cab4Me - Gives you Cab numbers of closest cab companies
TuneWiki - Good Musicplayer
AndNav2 - Free SatNav, bit dodgy but free (Copilot is better but you have to pay)
Astro - File navigator, backup apps, image viewer - v v good app.
aTrackDog - tells you what apps need updating, useful.
Facebook Sync - Syncs your contacts with facebook pictures. (Find it here:
www.anda.pk)
Games:
Abduction
Labyrinth
Monopoly
Pacman
Throttlecopter
Bonsai Blast
Armadillo Roll
Light Racer
Shed load of decent soundboards - ie Fonejacker/Arnie.