The citizens of the dock should need no introduction. Byline is a great RSS reader and Twitterrific 2.0 is just a killer Twitter client for iPhone. Wikipanion is a pretty good Wikipedia client, but I also have a bookmarklet for m.wikipedia.org on there too.
Since my wife got an iPhone, we've been experimenting with using AIM in place of SMS, but I don't think that experiment is working out. I usually install Instapaper when I have a backlog or plan to travel. The Compass app is alongside Maps because that seemed like a good idea, but I don't find myself using it much.
The next set of apps are those apps that I do use frequently, but don't need to be on the Essentials page. WordBook and my eBook readers are in here, as well as the ever-awesome PCalc. People have been cynical about Birdhouse, but I find it worthwhile.
I'm a bit of a sad case in that I have been heard to exclaim "Bah! Games!" about the App Store, then I realise that I have more games on my iPhone than any other kind of app. Firemint Real Racing is sensational. Real Tennis is hard to play.
This is my page of apps for travel, either in the UK or abroad. Controversies about the sharp business practices aside, the National Rail app is really very well done. If only the actual trains were that good.
Here go the things I need once in a blue moon but which I do want on my phone. Other apps that I only very occasionally want, I'll usually delete and re-download from the App Store as needed. These, I keep because when I do want them, I don't want to re-download first (for example, Shazam).
This page is mostly "Stuff that Apple won't let me delete". The Camera app goes here, because my double-home-tap action is set to Camera, so I don't need access to the app icon. Oh yes, and the secret app? I could tell you, but then....