Compare coverage maps in the areas you frequent and put the carriers in order of coverage. Then compare the plan prices. Once you find the carrier(s) with best coverage, pick the one with the best prices.
Then look up that carrier's phones and do a little googling to see if they have anything a lot better coming out in the next few months. If they don't have any big updates coming out for a while, buy their best handset. If they have something new and improved coming within the next few months and you can wait, then wait for the new phone.
Right now Verizon has the Incredible, AT&T has the 3GS, Sprint has the Evo coming in another 2 months at most, and T-Mo has the Nexus One. There are also new Dell Android and Win Mobile phones in the works as well as a new iPhone that will probably be on at least AT&T and possibly other carriers.
Choose based on coverage, then price, then pick your handset. Not the other way around.