The key on what to look for is going to be a world GSM phone, you'll want GSM 850/900/1800/1900 (and probably UMTS 850/900/1900 3G) band support to ensure you get both US and UK coverage.
Here's a great tool to try and work out what sort of phone would fit you best for your needs:
http://www.gsmarena.com/search.php3Android would probably be the best flavor to work with, and keep in mind that you don't need live data access to do GPS, it's a waste of money and bandwidth. There's offline map options from
Google Maps, to
Sygic, to
Navfree.
As for carrier, unless you plan on making a lot of calls and using a crap-ton of data, I'd recommend looking into
Truphone SIM. You'd be able to set both an inbound US
and UK number to the same account and phone, get free incoming minutes and texts, and get charged 9¢/minute/text/MB outbound with those rates being good both here in the US and over in the UK. If you figure calling will be minimal but heavy data use is needed, find a nice
dual-SIM model phone and pick up the cheapest prepaid SIM card with a data only plan while you're there to couple with the Truphone SIM. That said, don't forget about WiFi access.