Background: I've started documenting some of my favorite medium-difficulty and advanced-difficulty runs in the San Francisco bay area. The advanced runs are for extreme runners who are masochistic, at best. You can find out more about me here.
The Bayland Preserve (near Shoreline Ampitheater)
A good choice for quick, flat 3-8 mile runs. There are a few artificial hills with nice south-bay views -- throw them in for a challenge when you feel like it, or avoid them altogether. The view of the bay is nice when it doesn't smell (it smells in the late summer/fall), but it is kinda windy. I usually run around the shoreline hill, then along the trail along the edge of the golf course, heading south. Eventually, the dirt trails keep going until you get to where you can see Moffett Field (big Air Force base, you cannot miss it). These trails eventually swing back around along the edge of the bay and brings you back to the golf course clubhouse. You can keep running around the cute little golf course lake. Alternately, skip the stretch by Moffett Field, and just run around the cute little lake. There's also a whole set of trails that take off from near the end of San Antonio road (where it hits the bayland). You can actually start down by the baseball fields at the end of embarcadero road, run by the airport, through the baylands, and come back along bayshore road (it's 8-10 miles).
Stanford Foothills (paved, view of south bay, moderate hills)
Drive to Stanford, basically. Take 101 to PageMill/Oregon Expressway, Right on El Camino, Left on Stanford avenue. Drive until you Stanford Avenue ends and you see everyone parking...park with them at Junipero Serra.
Paved 4 mile loop trail runs up to and along the top of the foothills with stunning views. The climb is moderately difficult (e.g., you'll struggle for 5 minutes, but once you reach the top, you'll be OK). Many Stanford students run there.
If you're feeling rebellious, you can try to outrun the 4-wheeler patrol men, and run "backside", that is to say, the backside of the foothills. There's a trail that runs along the freeway, and down to old pagemill road. Watch out so you don't trespass on any farmer's property.
The Arastradeo Preserve (unpaved, wildlife/ponds, flat/hills optional)
This park isn't very well known, so you won't find references to it elsewhere.
Directions: Take Hwy 101 to Page Mill/Oregon Expy, then take Page Mill all the way under I-280 (about 10 minutes). Once you go under I-280, the road curves a bit, then you come to a stop sign. Make a right (the road is Arastradero), and drive until you see rolling hills with grass and trees -- there is a parking lot on the right which stays open until dusk.
The main trail (mostly gravel and dirt) winds up through a valley and along a few very quiet ponds. There are hilly ridge trails you can take if you want some amazing views of the south bay. They also let you do loops. Otherwise, a simple out-and-back along the valley can work out to a nice 3-4 miles (or more, or less, as you choose). This gets a bit hot in the peak heat of the day, because the trees don't give much shade.
Crystal Springs (dirt, view of lake/hills, some hills)
If you can find it, and don't mind wind and sun (e.g., it's fully exposed), Crystal Springs has *amazing* views, and some moderate hills (2 big hills which can be avoided -- or taken slowly/quickly at your pleasure). As for location, it's near where Hwy 92 and I-280 intersect, and it overlooks the San Andreas Rift Valley with its beautiful lake from a plateau ~500 ft above I-280. If you've ever driven north on I-280 and seen the "Vista Point" pulloff, this plateau is *above* Vista Point. Yes, with even better views. You drive to get up there -- directions are below.
It's a pretty famous race course, too -- it's often used for high school and college races. Special thanks to Bob Rush for all his work to maintain the course -- it has now been around for an astounding 30+ years and 100,000+ athletes, and some of America's more famous distance runners have raced there. Here are a few excerpts from Bob about use of the area (mostly w.r.t. races):
Crystal Springs Cross Country Course is in its 32nd year. We are hoping for many more. The use of this facility involves many areas of responsibility. The course is located on land owned by the San Francisco Public Utilities Commission. It is also a State Game Refuge. It is also located adjacent to a very sensitive residential area. The permit to use this area as a cross country course has been granted to the College of San Mateo. The fall weather in this area can become quite hot. This situation has to be taken very seriously for the safety of the runners...You can find the full course handbook online.
--Bob Rush, Crystal Springs Cross Country Course Coordinator, College of San Mateo
Directions: There are directions on the San Mateo County parks website (see below), but it's still pretty hard to find. The entrance I'm familiar with is behind the tennis courts at Hallmark Park (Google Maps link), which is along Hallmark Drive. Exit 280 to 92 East, exit Ralston avenue to the South, and make a right onto Hallmark Drive.
Rancho San Antonio (unpaved, wildlife, some hills)
This park comes highly recommended, but I've never run there because it is south of where I drive. It's in the hills, but I think it offers mostly flat trails with optional hills as challenging as you want.
This is an excerpt taken rom the PA running club: "Take 280 exit at Foothill Expressway, toward hills then right at the traffic signal onto Cristo Rey Drive. Go about one mile and turn left at sign for park. The trails begin near the Restroom area. There are miles and miles of hills, trails, woods, etc. You might see deer, bobcat, wild turkeys, rabbits, and snakes."
Huddart Park (unpaved, wildlife/redwoods, hills)
No way around some moderate hills here, but you'll get rewarding, soft redwood trails with a very quiet, natural setting. If you get a map, you can pick a moderately flat path. Even the flattest trail (Richards' Road) has some hills you may want to stop on. ;)
I usually park near the Woodside Store, so I do not have to pay to get into the park. Take Woodside Road through Woodside the town, until you hit Kings Mountain Road on the right. There is a sign for Huddart Park. If you drive over a bridge, you've gone too far. Take Kings Mountain Road past some big estates, and find Tripp road on the left with a historic monument (the Woodside Store). Park along Tripp road near the store (they close the gates at ~4pm). Alternatively, continue driving up Kings Mountain Road until you reach the park entrance.
About another 100 ft up Kings Mountain road is a road to the right called Greer road; there is a dirt path along it leading to the park's back entrance. Once you enter the park at the horse gate, find the only dirt trail, and cross the long footbridge. The trail winds up a hill a bit, until you come to a field with a bathroom. The trail that takes off at the gate is Richards Road which you can run on for a long ways.
Eventually, Richards road makes a 160 degree turn -- if you want to keep going, there is a small trail which veers off to the right, and follows the river valley into the Phfleger Estate and the Golden Gate Nat'l Recration Area. This goes for many, many, many more miles. For a nice finishing hill and loop before returning, instead of making a right at the 160 degree turn, go straight, and head up Crystal Springs trail. Go past the Canyon Trail. Then make a turn onto Chaparral Trail. This leads back to Richards Road. total add on is around 3 miles.
I recommend a map (found on the San Mateo park website below); they also have them sometimes at the bathroom.