It does matter which phone you get. Each carrier uses a different protocol (CDMA, GSM, TDMA, iDEN, PCS, AMPS - which is analog) on their networks for communications. For instance, the new iPhone can only access the AT&T network. A Nextel phone only works on their towers. A Verizon phone only works on their towers, which is why you see the cell phone companies putting up towers of their own, and not sharing. They compete heavily on infrastructure and that investment, which is why they all have different strengths in different areas. Sprint is terrible - not enough towers.
Oh, and only CDMA (Verizon) also has analog, or maybe an older TDMA (AT&T) phone, but good luck finding it in a store. Dual band phone, one number, it switches automatically depending on availability of signal. Analog sucks down the battery.