I'm a Verizon customer and I agree that they've got the best back-country coverage in California and Utah, where I've used my phones.
My smartphone is a waterproof, dustproof, highly shock/freeze/vibration resistant Android unit from Casio, called a "Commando". Say the name with rumble in your voice, like the announcer for a monster truck commercial, thank you. I can confirm the phone is waterproof down to 8 feet at least and it's spent a good part of a few days in lakes and rivers (in my submerged side pocket). It's also survived a number of drops, tumbles and such on asphalt, rock, dirt and a streambed. Since it's pre-built with the armoring and uses a thick Corning Gorilla Glass screen, it doesn't need an auxiliary case and I don't use one. The batteries pop right out and I backpack with an extra charged one.
I use the phone for email "bursts" at night and as an emergency communication device, but I don't turn on the battery-sucking GPS, generally. I keep the phone turned off when I'm not using it or don't need to play Angry Birds, ha ha!
The downside to the Commando is that it's slow. It uses Android 2.3.3 and has limited onboard memory. Compared to my wife's Samsung Galaxy/Fascinate, it's dull and sluggish. However, it's also survived quite well and I don't actually play Angry Birds.
Casio has a 4G-LTE version coming out, but not until the Christmas shopping season, 2013, by most estimates (revised from Jan'13). If you want the battery-swap capability, there are a number of other phones that now offer a version of Gorilla Glass, Android and some water-resistance. The Commando goes for $99 or less right now, too.