Just returned from a two-month run, from the East Coast to Seattle and back again. My experience with cell coverage, using an inexpensive ($50) dual-mode Kyocera phone (QCP 2035a) was excellent. Coverage almost everywhere, digital about 80 percent of the time, a bit higher near the Interstate (I did have analog coverage in large areas including southern Utah, and the Oregon coast.) I use the phone with Verizon's modem connection kit (about $70, I seem to remember) with excellent results.

Truck stop suggestion: If you're looking for a stop where you can plug in using your laptop and analog modem, the Pilot chain was the most helpful to me. I don't think I ran into one that didn't offer a data jack. Love's, Flying J, TA, Conoco and other truck stops were a crap shoot, but Pilot came through consistently. Kudos.