AT&T and Verizon should work well on your cruise. I have an iPhone with AT&T and had signal for the whole trip. I have been a few Royal Caribbean cruises this year, 2 Western cruises and our phones worked just fine. It is costly though. It was $2.50/min and $.50 text. If you have an unlimited messaging plan, incoming text are free. Make sure Data Roaming is off on your iPhone, if you don't want to get charged. If i recall it is almost $30 per megabyte when roaming. AT&T sent me a text informing me of this once the phone started roaming.
All the ships I were on had wifi on board and it was $.50/min Pay-As-Go type plan. If you wanted to purchase a wifi package and price per minute was a little less. I normally get a $5.00 coupon for free Wifi and tried to call my parents using Skype but It would not connect when trying to video chat. When I tried calling a landline it worked fine with no lag. I did not get a chance to try Facetime. Checking email and surfing the internet is a bit slow because of the satellite connection. If you are going to use the wifi, use it on off-peak times. The crew gets a discounted rate so you are sharing the connection with them too.
What Ports are you going too? I usually find some free wifi at the ports. If I have been to the ports your are going to I'll let u know where to find some free wifi.
Once on land at the ports, for sure the AT&T phone will get signal since it is GSM, but i don't think your Verizon phone will work since it is CDMA.
