Someone here mentioned TING in another thread... They use the sprint network. I ordered some used, unlocked Samsung Nexus S phones off of ebay ($45 each), and activated them on Ting... Our bill for 2 smart phones is less than $40/month.
We were paying $90/month for two "dumb" phones with Verizon. The signal was better with Verizon - but Sprint is upgrading the network in our county to 4G - so it should be getting better.
I also have an android tablet. It's wifi only - but it works great for all my uses during travel. We have an old unlocked GSM dumb phone for travel to Europe - we buy a sim when we arrive - and then text the number to relatives.