I do get Sprint and Verizon in my area (and even TMOBILE) which is nice but also makes it more confusing! We are going to get service by this weekend because my wife is on the road alot for work and needs a phone ASAP so unfortunately I cannot wait too long for a new phone to arrive.
Right now after going out and playing with some phones it comes down to :
Verizon: Omnia or Storm
Sprint: Pre or .. well they don't have much else
TMOBILE: Samsung Memoir, G1 (seems slow and date though) Curve 8900
If you have T-Mo coverage why not just pick up an iPhone and unlock it? Yeah you can't get the 3G S (last I checked), but the 3G is still a dam good phone.