Consider a Google Android phone.
Unfortunately, at least in v1, the Google Android phone is no where near as slick or useful as the iPhone. It's a nice first outing, and is much better than any current Windows Mobile device in many of these regards, but it is no iPhone killer. The Application marketplace is no where near as developed, the over-the-air purchase and downloading features are not anywhere near as slick or developed (a web-ui will never cut it, it needs a custom application), the audio and video player functions are no where near as slick or useful, and the whole UI of the phone isn't consistent. It feels still a little too much like a "linux device" and the UI Guidelines aren't even followed by Google consistently, much less by the independent app developers. Plus, the touchscreen on the current HTC G1 is not the same as the iPhone's at all. This isn't just it's lack of multitouch (which seems to be more of a software and CPU power issue than anything else), but the phone lacks a dedicated GPU, which severely limits its ability to function as more than a phone/web browser/audio player.
Hopefully they'll catch up in a few versions. I'm skeptical though... One benefit Apple has here is that they control the entire platform. Google will, I'd guess, quickly run into the problem of trying to support a widely varying set of different hardware platforms and capabilities.
That, and go ahead and bring that T-Mobile phone up here where I live, Jim, and you'll see why I need AT&T or Verizon. T-Mobile and Nextel/Sprint stop working pretty close to the state border, and certainly don't work up here near Bar Harbor and Acadia National Park. With AT&T I don't get 3G (yet, supposedly they're upgrading "soon"), but it generally works a bit better than my wife's AT&T Nokia.