They've been out a while now, so you guys must have got a few good ones by now?
My personal favourites:
Manifesto - I only just discovered RSS (I'm quick me). It's great...
Drop7 - The best puzzle game since Tetris. I go to sleep at night thinking up new ways to link lines and get combos.
BrainTuner - Good for a few minutes of testing your old grey matter out.
LastFM - Obviously...
iFooty - Great way of getting live match feeds for your team.
MyRailLite - Have the entire country's train timetable in your pocket.
RjDj album - Samples the sounds around you and creates new pieces of abstract music and background sound.
Shazam - Mighty handy for finding out tunes you don't know the name of.
Trace - A clever little game where you have to draw the levels to reach your goal.
Solitaire - Everyone needs it.
RF09 - Like Fifa on the PS1.
I'd also use the BBC iPhone enabled iPlayer and Podcasts pages, if I had access to Wifi more than I do...