I have a few gems that I go back to again and again and wondered if theres a lot I'm missing out on? Here's the ones I love. What do you recommend?

Games

Bejeweled 2
Pocket God
Doodle Jump
Fling
Flight Control
Penguin
Geared
Mr AahH!
Implode
FallDown

Movie/Music

Flixster - movie reviews/cinema info
Shazam - tells you the song you're listening to
TuneWiki - streaming radio/lyrics

I don't really play games but I have a couple of really useful apps I find myself using all the time...

Delivery Status Touch
Tioti TV+
Pocket Alan (just like having Alan Partridge in your pocket!)
iPeng

A bit of a rubbish list I know.

Cheers

Cris.

Civ Revolution

Apps I use frequently:

BeejiveIM - Decent IM client with push support
Gowalla - Location based game, similar to Foursquare
Mint.com - Financial program that integrates with the web site
BBCReader - Nice BBC news app, includes offline mode
Sim City - Has a feeling somewhere between 2000 and 3, been slowly building out a city
Peggle - Wishing they had Peggle nights out as well
Tile Poker - Fun little Poker meets Bejeweled type game, made by a former artist coworker

Oh, and i.wund.com is a site I use for weather, added it as a bookmark on my home page. Really handy for the wundermap to see the next major hailstorm coming into the area.

Utilities:

Remote (connect to iTunes on my home network)
Shazam (recognize songs)
Facebook
TweetDeck (Twitter client)
Pandora (listen to tunes)
P-Calc Lite (decent RPN calculator)
Instapaper (read web sites that I flag for later reading in my browser)
Skype (when traveling abroad, seems to work)

Eye candy:

Bloom, Air, and Trope (ambient music gadgets written by/with Brian Eno -- my daughter digs these)

For me... (on top of many of the others mentioned)

Yelp (way preferable to the website when mobile)
Slacker radio (less effort than pandora)
Simplenote (excellent notepad that syncs with an ajax notepad you can get to from your desktop)

Great thread! I always ask iPhone owners if they've found any cool software. My favorites are:

iBird Pro (Birding application, good enough to replace my field guide)
i41CX+ (excellent implementation of the HP41CX)
i48 (usable implementation of HP48GS)
TouchTerm (ssh client)
TripIt (awesome for business travel)
ExitStrategy (the best New York subway app I've found)
Now Playing (best movie showtime app I've found)
PhoneFlicks (add to your Netflix queue)
MPR Radio (Minnesota Public Radio, worth it for The Current)
Public Radio (all the public radio stations in the US)
Pandora
Shazam
Flight Control (game)
Scrabble (horrible software, chews battery, but the only alternative)
Subway (great puzzle game)

While I don't currently have an iPod (waiting for Hugo to finish pimping the 4th Gen iPhone ) here are the apps I use (using wifi whenever required):

VNC (VNC Client)
Zenbe (Makes lists and allows you to sync them online)
UK Numbers (Convert areas to telephone area codes and vice versa)
Remote (Apple iTunes remote)
Air Sharing (File drop box over wifi)
eBay
Stanza (eBook reader)
TC Calculator (Converts ordinary times to timecode and vice versa)
Moonlight Lite (Mahjong game)
Enigmo (Water-based puzzle game)
Days Until (Stick a date in and it tells how many days until the event)
Sound Box (Play sound effects on the device and also trigger remotely via a web page)
iDaft (Daft Punk in a box)
London Tube (Tube maps and route planner)
Tone Pad (Mini Tenori-on)
Amazon UK
thetrainline (UK train times and journey planner)
The Stig (Nuff said)
Codec Calc (Data rate calculator)
Remote (Apple keynote remote, you too can be Steve Jobs!)
Spotify
Flickr
Solitaire
Now Playing (UK cinema listings)
Sonic 1 (Full game running on virtual Mega Drive/Genesis)
Convert Units (Convert between units)
Your Orange (Orange account status)
RAC Traffic (UK traffic status)
iPity (Mr. T based office productivity tool)

..and finally, not so much an app but a url:

http://iphone.tvcatchup.com/

Almost as useful as iPlayer.

Nice!