OP said that he wants to swap a SIM - I think that means he needs T-Mobile (yuk for coverage) or AT&T (just a little less YUK). Go look in the Howard Forums
to find guys and gals that really know this stuff....internationally.
That said, in my travels all over NM and a bit around the rest of the country - Verizon rocks. The sad part is they know it and are move expensive. I spend a fair amount of time in rural NM, but this year, for the first time, did not have coverage when othesr did. Talking to folks there the ONLY provider was a local company. Very odd IMHO.