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)