Couple of points:
Calif. State Parks don't allows dogs on trails, similar to National Parks, so that's quite limiting.
Ticks. Everywhere I've taken a dog on trails in the Bay Area or the coast, its accumulated ticks. Also have to keep it on leash to keep it out of the poison oak.
The Sierra Nevada is a whole lot easier with a dog, but a longer drive of course. Since we're deep into a drought most of the foothills are quite open, as are some exposed parts of the main range up to 5-6000 feet. You might check out some of the river drainages--Feather, Yuba, American, Stanislaus, etc.