Shazam - great for when I hear a song while out and about and can't remember the name/artist. I also use it to keep track of songs I want to download at a later time.
Ping! - free texting for iphone-iphone. Great for those of use who have several friends/family members using iphones but don't have unlimited texting.
The Weather Channel - better app that the standard weather app
i.TV - 3-in-1 app - TV listings, set recordings for TiVo, and browse/update Netflix queue.
Wikipanion - I'm always looking up random stuff
BeejiveIM - one app for various IM clients (AIM, MobileMe, Google Talk, Windows Live, etc.)
Cardstar - I keep all of my infrequently used store card #s in there so I don't have to carry the actual tags or cards.
Social apps - Facebook/LinkedIn
Twitter apps - So far my fav is TweetDeck, but I'm testing out Twitbird right now. Previously tried Echofon and Twitterific. Might give Echofon another try.
Simplify - When I had my desktop up and running I loved this app. It allows you to stream music from your itunes.