Thank you, everyone, for your suggestions. I now understand my requirements a bit better.

- I don't need Skype in particular, but I do need a voice chat application I can use over WiFi. Google Talk with voice chat would do, or any other easy-to-use alternative. Maybe SIP? Fring? The point here is to use WiFi for audio calls to avoid an expensive data plan while travelling.

- Still need GPS + maps.

- T-mobile 3G is important, and that rules out just about everything from Nokia except for the 5230 Nuron, but the lack of WiFi rules out that one. Grr.

- The Nexus One and Samsung Behold 2 are great phones, but pretty expensive.

- I'm willing to bend on the OS.

Is there a Tmo G1 in my future?