You've actually got a few options with T-Mobile.
MyTouch4G: My brother has this, pretty nice. He upgraded from a POS Cliq. The downgrade, it's got a custom skin (2.2 Froyo) on top of it (meaning, it'll take some time to get the newest version of Android when it gets released).
G2: I got this as a replacement for my Nexus One. I had to get my brother a new phone because the Cliq was a POS and they upgraded both our accounts with Buy One Get One Free. So I tried the G2 and couldn't go back to the Nexus One. It's bittersweet because I've spent over 700 on the Nexus One with all its accessories. The G2 is also vanilla (2.2 Froyo) Android (no skins on top of it.)
Both the MyTouch 4G and G2 are HSPA+ (4G) phones.
Samsung Vibrant: Nice phone with lots of internal memory as well as a external SD card slot. My friend has it, loves it. Samsung likes to lag in updating their phones to the latest Android version, so beware. Has a custom skin (JUST got updated to 2.2 Froyo).
Nexus S: The second phone made specifically for "Google." Has vanilla Android and is the only phone to date with version 2.3 (Gingerbread). It'll be the fastest phone updated to the newest version of Android as they come out. Very similar to the Vibrant except that it does not offer external storage. So if you start running out of memory, tough luck.
If you can wait a bit (~1 month):
Samsung Vibrant 4G: Just like the Vibrant except it's T-Mobile's fastest 4G phone to date. It may have a few more advantages that I can't think of right now.