I'd likely go to T-Mobile as well. Thought about Sprint, but Phoenix isn't on their list of LTE cities and their 3G coverage here is a joke. Whereas TMO is actually pretty good. Plus, they have the advantage of being a GSM carrier, and once they flip on that spectrum from AT&T's failed hostile taker over, one should be able to take a very wide range of international devices onto their network.
Hypothetically, if a Verizon customer was fed up and wanted to change carriers once their contract was up, what order would you have to do things in to keep your existing phone number? Assume the customer in question would purchase a phone from the Play Store.