Last time I checked, Cingular (formerly PacHell) is the only GSM provider in the Bay Area.

You could try lobbying Voicestream to move in (IIRC they have presence in all the states EXCEPT California & Nevada) -- they seem to have a better reputation.

AT&T is going to GSM/GPRS, but:
1. I don't believe their current network in the Bay Area is GSM, because they bought it from Cellular One, which was not GSM
2. You still may be screwed, because in the Western US (but not including CA & NV), AT&T and Cingular are cooperatively building a GSM network, so their coverage would be the same. They may do this in CA too.

Not every GSM phone can take advantage of switching carriers, e.g. if you buy it from the carrier, they can lock the phone so it won't accept "foreign" SIM cards. For example, my pre-paid German GSM phone won't accept an Italian SIM card (from a different network). However, I don't think you'll run into this problem.

You may want to look at non-PacBell options for SMS; for example, bigfoot.com has a service that will send SMS messages from a computer.

If you do not use you phone a lot, you might consider changing to Cingular Pre-paid; its terms are lousy compared to European pre-paid, but better than most US pre-paid carriers ($20 card expires in 90 days IIRC).

Good luck, and I'd recommend bugging Voicestream and AT&T to find out what their plans are.

Tony