Android phones on T-Mobile have tethering enabled. At least my still-locked HTC G2 does. As far as I know, I'm not paying extra for it.
As far as we know T-Mobile is a lot more "customer friendly" since they're running 4th out of the big 4 Wireless provider in the US.