Nexus 1.

The easiest phone I have ever set up.

You just need a google mail account. You don't have to actually use it for mail, though.

It's the best phone so far. Yes it's not perfect, but no phone is... yet.

I use it in the Uk and Suisse (with O2 and Swisscom SIMs), and it's easy peasy.