Travel with an iPhone

• O2 50MB international data bolt on (it's £50 for a month, but better than £6/MB otherwise; just remember to cancel it afterwards).

Maps

• Google Maps (built-in) - indispensable for maps, routing (driving, walking and especially public transport) and Street View.
• OffMaps - download maps on wifi in advance, for offline use; now includes some routing.
• RouteBuddy Atlas - OpenStreetMap, OpenCycleMap and purchased Ordnance Survey maps (though they're really expensive).
• iTrail - record GPS tracks (just remember not to switch the screen off; not sure if this is still the best of its kind, I haven't looked at the others recently).

Nearby

• Yelp - brilliant for restaurants
• Showtimes - cinema listings
• beeloop "At A Glance" City Guides - I like the "What to do now?" feature, though only the San Francisco version is free. It could do with reasons why places are recommended, too.
• Dopplr - the best presentation of all the "nearby" apps so far, but doesn't have many places listed yet. Also good for adding data, with the "I've been here/I liked it".

Other

• TripAdvisor (website, for hotel reviews).
• Expedia (website, for hotel and flight booking).
• WeatherPro - weather forecast.
• Instapaper - reading material saved for later.
• Stanza - more offline reading material.
• Byline and TwitterFon - for keeping up to date.
• Skype - much cheaper international calls, when on wifi.
• Flashlight - for seeing in the dark.
• London Bus - London journey planning (not just buses) and bus routes.
• National Rail - UK trains.
  
• TubeDeluxe - London tube status.