Verizon covers most of the rural areas that I go to. Get a dual or tri mode phone. If you go into rural areas much, you'll lose a digital signal, so analog will be all you can get.
I've had pretty good coverage with Verizon on and around the Sky and Skagit. Still haven't found anybody that covers the Tarheel country between Darrington and Rockport though.
For coverage between Darrington and Rockport, try two Campbell soup cans and a length of twine. (length to be determined by the clarity of the signal desired.)