When you say "DC would be free" - by "DC" do you mean Nextel's "Direct Connect"? If so, then you are using a Nextel iDEN phone, and this limits your choices substantially.
There's three main cell phone network technologies in the US:
1. GSM - this is the system used in Europe and most of the world. In the US, AT&T and T-Mobile are using the GSM system.
2. CDMA - this is the second most popular technology and is used in the US, Canada, Mexico, China and India. In the US, Verizon and Sprint use CDMA.
3. iDEN - to the best of my knowledge, the only major carrier that uses iDEN is Nextel - and a lot of Nextel customers are actually using Sprint's CDMA system.
The problem with iDEN is that very few carriers still use it. So that limits the phone choices substantially. Since, iDEN was developed by Motorola, they support it pretty well. And since a lot of companies use iDEN Direct Connect and Group Connect for their technician and support staff, Blackberry supports iDEN somewhat.
Personally, my favorite iDEN phone is the Blackberry Curve 8350i. GPS, web surfing, email, camera... that's what I'd get if I needed an iDEN phone. If it's too big, for you, then my next pick of a fancy cutting-edge phone would be the Motorola Stature. If this is too expensive, then the Motorola i760 is a good all-around phone with good call quality and good battery life if you turn off a lot of the features.