You’re going to have to split your purchase. Get a phone from whomever is the best in your area (Check with friends to see who is the least bad). For overseas travel, the only way to go is to get an unlocked GSM phone (6th Avenue electronics, Amazon, and others sell them). You can get a phone that is good for voice and SMS for under $100 and then purchase a prepaid SIM locally.
Then use either Google Voice or Skype to direct US calls to your phone overseas. Truvoice is another option (and they have their own SIMs).
CDMA ( the tech used by Verizon and Sprint) is basically a US only system, no matter what Verizon says. They have some phones that are CDMA and GSM, but they are expensive and locked to VZV’s partners at high rates.
CDMA exists in much of Asia and South America; you have roaming costs to deal with, though, as you cannot "swap identities" of the phone like you can with a SIM card, which is why a dual-technology phone is VERY nice (like most of the newer HTC phones).
They have some phones that are CDMA and GSM, but they are expensive and locked to VZV’s partners at high rates.
Only if you stick with CDMA overseas; to unlock my HTC Touch Pro 2 I simply had to walk in to the local Verizon Wireless store, and tell them I wanted the SIM card (GSM radio) unlocked for overseas travel. Literally 3 minutes later out I walked with a fully-unlocked phone, and it uses my overseas SIM cards seamlessly when traveling. No charge, no cost.
You can do it over the phone, too, if you like... Verizon will give you the unlock code with a 2 minute disclaimer that if you have problems on your foreign/non-Verizon SIM card you're on your own. Other than that, it's about as easy as you can get.
So you can benefit from the MUCH better Verizon network here in the US, and still get the advantage of SIM card swapability overseas if you get a decent phone that runs both technologies.