The right answer is Nexus One on T-Mobile. I am not a huge fan of tmo's coverage here in San Francisco, but they have the best plans for what you want, I think.

Nexus One because it's unlocked and also: it's the phone that Google employees use most therefore your phone will run the newest builds/features before everyone else's.

When you get it: immediately root it ("fastboot oem unlock"). If you want to do it later, it will wipe your data first. And then toss the latest Froyo build on there - you will have to Google around to find it, but it's really good.