This is an incomplete list of places worth trying "over the hill", mainly in the South Bay and some Peninsula areas as well. Unless otherwise noted, it's based on personal experience. There is a lot of great food here, especially Asian food, and I hope this helps guide you to some interesting places.
I link to many Yelp websites below when I couldn't find a decent website for the restaurant itself. I don't necessarily advocate reading their reviews (they're uneven at best), but the address, hours and map are useful. If you want to do your own research, I highly recommend Chowhound instead. At the bottom are particular Chowhound threads that I hope will be helpful for you to do your own research.
Updated April 30, 2012
99 Ranch: There are a bunch of 99 Ranch locations in the Bay Area. While there are other Chinese grocery stores, these have always suited my needs.
There are two large shopping plazas in the South Bay which are predominantly Chinese. Each is anchored by a 99 Ranch (whose location I'm linking to below) but each has a whole ecosystem of restaurants, video stores, book stores, tea shops, etc surrounding it. If you're flexible and up for a bit of an adventure, just go to one of these plazas and try one of the busy-looking restaurants - there are many choices.
Cupertino Village: Besides the places described below, there's are a couple of decent bubble tea place (of course) and a Sheng Kee Bakery (try the Portugese custard tart).
Milpitas Square: Probably an even wider restaurant selection than at Cupertino Village. On my list to try are the Shanghainese place and Darda, a Muslim Chinese restaurant (try lamb dishes, hand-cut noodles and the sesame bread). There's also a decent Malaysian place, New Penang Garden which is plenty serviceable. There's also a Sheng Kee Bakery here.
A&J: [Cupertino Village] Northern Chinese hole-in-the-wall. Get potstickers; pan-fried beef bun; beef noodle soups; fried (sometimes called salt and pepper) pork-chop. Requires a bit of an adventurous spirit if there isn't a Chinese speaker. I'm a big fan.
Joy Luck Palace: [Cupertino Village] I mainly go for the dim sum, which IMO is the best at the moment in the South Bay (i.e. if you don't want to venture up to Millbrae). Arrive before 11:30 am or so, otherwise expect to wait for a while. Also has good Cantonese banquet-style dinners (though Mayflower probably does this slightly better).
Southland Flavor Cafe: [Cupertino Village] Taiwanese. Decent for a quick meal. Get something like the pork chop rice or chicken rice if you're by yourself. Most notable is that they sell frozen handmade dumplings by some grandmother in 50 count bags for $13. Just go to the cashier and ask them. It's not on the menu. Choices are pork and chive, pork and cabagge, and Shanghai-style xiao long bao (mainly just pork filling) - the latter are more expensive. I'm a bit fan of the pork and chive myself. They're about a hundred times better than anything in the frozen section of 99 Ranch or (shudder) Trader Joes.
Hong Kong Saigon Seafood Harbor: [Sunnyvale] Yes, weird name. Cheaper than Joy Luck for dim sum with commensurate decrease in quality. That, of course, also makes it a magnet for the younger crowd. Again, go early-ish if you don't feel like waiting for 1 hr or more. If you have an extra five bucks to spare, please go to Joy Luck instead.
Queen House: [Mountain View] Taiwanese. Noodle soups and lots of other dishes.
Mayflower: [Milpitas Square] There a few branches of this Cantonese banquet restaurant around, but the one in Milpitas is closest and most convenient. I'm not a huge fan of their dim sum, but they are rather good for dinner.
Shanghai Flavor Shop: [Sunnyvale] I haven't visited yet, but it is widely acknowledged to have good steamed dumplings (a.k.a. xiao long bao a.k.a. "xlb") and particularly for their pan-fried pork buns.
South Legend: [Milpitas] Sichuan. If you've never had Sichuan food, come talk to me for a list of suggested dishes since it's not your standard Chinese menu.
Mama Chef: [Santa Clara] Taiwanese. Pretty decent Taiwanese at that - not stellar, but more than serviceable. Very inexpensive with a wide range of Taiwanese street dishes. If you don't know what to order, come talk to me (or Erinna). I've heard recent rumors of it going downhill, but have not confirmed them myself.
Shanghai Delight: [Milpitas] Shanghainese, obviously. Some very good dishes, some so-so dishes. There are dishes here that I'm told are very hard to find anywhere in North America.
Chinjin Eastern House: [San Jose] Islamic Chinese. Good to excellent Islamic Chinese dishes. They have house-made knife-shaved noodles, which are fantastic. Their "Chinese hamburger" which is really a large pan-fried beef dumpling, is huge but not quite as good as the ones at A&J. Cumin lamb and sesame bread are also typical dishes.
Tong Dumpling Pot: [Cupertino] Chinese dumplings. Everything is made in-house. Wide-array of fillings. You can get them pan-fried or boiled. All the ones we tried were very good. Scallion pancakes also very good. Also sell their dumplings frozen, but I think you need to pre-order.
Michelle's Pancake House: [Cupertino] Northern Chinese. Despite the unlikely name, a very popular and new branch of a Southern California restaurant serving "pancakes" which are really pan-fried buns with things stuffed in them. I've never actually tried it; the wait was something like 45 mins on a Saturday lunch when we tried to go. I'm told everything is house-made and I'm eager to try it. Their website doesn't seem to acknowledge (yet?) the Cupertino location.
Shanghai Garden:
[Cupertino] Also Shanghainese. The fish in wine sauce is awesome and
extremely authentic. I've heard good things about their shengjianbao,
as well as their stir-fried rice cakes, both of which I really enjoy
when done well. I'll return to explore more of their
Shanghainese menu.
Almost all the great dim sum places in the Bay Area cluster near SFO (in Millbrae or Daly City).
Koi Palace: [Daly City] is often cited as best in the Bay Area, but beware the wicked lines, at least on weekends. Go early (or late?) or as a party of one or two and it's not so bad. The roast pork here is almost always excellent. Their dinners are also very good. You pay a premium for top-quality dim sum, by the way. It's a hybrid of menu-service and cart-service so you can get more obscure dishes hot and not have to wait for them to come by. I don't actually believe it's superior to the others in the area and in fact I'd rather to go to Asian Pearl or Zen Peninsula most of the time.
Hong Kong Flower Lounge: [Millbrae] I like this place just as much as Koi Palace, though it probably doesn't have quite as wide a range of dishes, but it's also slightly cheaper and the wait is slightly shorter. Update: It's changed hands now and the food quality dropped by half a notch. I'd recommend Zen or AP instead now.
Zen Peninsula: [Millbrae] Mainly menu-service. But flavors are clear and tasty.
Asian Pearl's: [Millbrae] Very good dim sum. Very clean and clear flavors and nice execution.
Crouching Tiger:
[Redwood City] Sichuan. Very good flavors. Somewhat dumbed-down by
default, but ask them to make it legit and they apparently will help
you out.
Da Sichuan:
[Palo Alto] Sichuan. Very good flavors. Not dumbed down at all. Need to
explore more of the menu, but their Sichuan dishes are totally legit.
Mitsuwa: [San Jose, near San Jose/Cupertino border]. Excellent Japanese supermarket.
Disclaimer: I'm a traditional nigiri sushi guy. I value the quality of the fish above all else. Next in importance is the selection of fish, i.e. the rotating "white board" specials. Occasionally I'll also order sashimi. If you want rolls, fusion sushi or whatnot, there are probably better places than these. And I only sit at the sushi bar, so I won't vouch for table service. Lastly, I try to go on the days that the top places get their shipments from Tsukiji, which are Tues and Fri.
For Peninsula sushi (south of SF to Sunnyvale, roughly), check out Sushi Monster's ranking of sushi places. SM ate at every sushi place possible. Amazing dedication to the cause. The SM site also has a wealth of information about eating traditional sushi. Note that the SM's top-ranked place is...
Sakae Sushi: [Burlingame] Is indeed the best in the Bay Area that I've tried. They've recently moved to a new location and opened a sister restaurant that I haven't tried. Best reason to go is to eat off the amazing white board. Pricey but worth it. Update: still the best. The quality of their fish is outstanding. And it's still more expensive than most.
Akane: [Los Altos] Sushi Monster's second-rated place and best value. I didn't much like the sushi bar ambience (small and a bit of an afterthought) and I think Kitsho's fish is generally better (albeit more expensive).
Kitsho: [Cupertino] Best sushi that I've tried in the South Bay. Much better if you sit at the sushi bar. Very good white board. They also have a range of cooked dishes which are quite good.
Sushi Sam's Edomata: [San Mateo] Top-notch sushi at (relatively) reasonable prices, which makes it probably the best value sushi place in the SF Bay Area that I've tried. Very good white board.
Sawa Sushi:
[Sunnyvale] Probably the most controversial "sushi" place in the South Bay. Plenty of love and hate. Here's a review from the seriously high-end blogger ChuckEats.
My take: It's not not really a sushi place, more like a
Japanese-inspired raw fish/crudo joint with a slightly crazy
chef/owner. He was very personable when I went, and the
ingredients are amazing, but it's not sushi or even sashimi. It's
also overkill, as each dish is probably twice to four times the size it
needs to be. It would be more pleasant if there were more, but
smaller, dishes.
I'm rather addicted to Japanese ramen. There are a number of great choices in the South Bay.
Santouka: [San Jose] It's in the small food court of the Mitsuwa grocery store and has exactly the ambience (zero) that one would expect. Also has great ramen. Their toroniku (ramen with pork jowl meat) is fantastic. Fairly high on the salt and fat content, though, so it's not health food (but no good-tasting ramen is, really).
Orenchi:
[Santa Clara] My
latest favorite ramen place. It's actually a restaurant so it's a much
nicer place
to hang out than Santouka. Broth is lighter in style than Santouka but
has good flavor. Update: this place is now the go-to place
for, seemingly, the entire South Bay. Lines can be ridiculous. Go
early or late is my suggestion.
Kahoo Ramen: [San Jose] In same shopping plaza at Mitsuwa. Get shio ramen; miso ramen; gyoza; kare-age. Their gyoza is the best I've had in the Bay Area. Ramen is maybe half a notch below Orenchi.
Halu Ramen: [San Jose] Some people think it's the bees knees. I prefer Orenchi and Santouka myself, but it's pretty darn good nonetheless. Try their special Halu ramen.
Maru Ichi: [Mountain View] If you're on Castro and need a decent but inexpensive meal, I'd try either this place or Queen House.
Ramen Dojo: [San Mateo] They're known for a substantially spicier style of broth, although you can order it non-spicy. I had regular spicy and it had a good kick to it. Tasty, but less subtle than regular ramen. Tasty and close to SFO but not worth a special trip IMO.
For more Ramen help, check out Melanie's Ramen Rankings (this links to a recent list - it doesn't actually change much over time at this point). I will say that I think Kahoo is too low.
There are a number of Japanese izakayas in the South Bay all serving a range of cooked dishes whose origin is essentially bar food, but it's evolved well-past french fries and jalapeno poppers. Easier to think of them as tapas restaurants. Small plates allow you to sample lots of interesting dishes. I haven't eaten at all of these often enough to distinguish which one is the best, but they all have their advocates.
Tanto [Sunnyvale]: Huge menu.
Gochi [Cupertino]: Leans toward fusion than traditional Japanese.
Hoshi: [San Jose] Go mainly for the "appetizers" and not sushi or regular cooked dishes.
Dan Izakaya: [San Jose] Had a really good meal there last time when focused on izakaya-style dishes. Grilled pork cheeks and kimchi fried rice were particular standouts but almost all dishes were very good.
Saizo: [Sunnyvale] Haven't tried yet.
Gokaku: [Cupertino] Good izakaya. Still a half-notch below Dan for me, however.
Yume-ya: [Sunnyvale] Next on my list to try.
Kappo Nami Nami: [Mountain View] Really interesting koryori-style (described by someone as seasonal, upscale, elegant Japanese) restaurant on Castro in downtown MV (lunch has a different menu and apparently not that interesting). If you're interested in a culinary adventure (with bill to match), give it a try.
Kaygetsu: [Menlo Park] Specializes in Japanese kaiseiki set menus. Expensive and very good. Update: closed.
Wakuriya:
[San Mateo] Like Kaygetsu, but less expensive. Haven't been but it's on
my list. Update: still haven't been, but the reviews are glowing.
Sumika: [Los Altos] Japanese yakitori (grilled skewers, mainly of meat). The food is fairly subtle (no strong sauces), meant to express the meat more than anything. You can order very specific meat parts (e.g. chicken breast, thigh, gizzard, heart, skin, etc.) as distinct dishes. My last meal here was very good.
Gombei: [4 locations - I've only been to the Japantown/San Jose location] Mainly for inexpensive cooked dishes. Curry plates, tonkatsu, croquettes, that sort of thing. The equivalent of a American diner - in a good way.
San Jose is home to a very large Vietnamese population so there are more restaurants than one could possibly try. For the adventurous, the Grant Century Mall (Story Road near the 680/280 interchange) has a food court with a wide variety of (I believe) authentic vendors dishing out all sorts of Vietnamese goodness. The stretch of Capitol Expressway east of Hwy 101 in San Jose also has a huge number of places.
Pho Ha Noi: [San Jose] Known for their northern-style chicken pho, which is more delicate than most typical pho. Make sure to get their housemade rice noodles which are excellent. Tip: do NOT douse the broth with hoisin or hot sauce since it will mask the flavors. Most customers will mix hoisin and hot sauce in a side dish to dip their chicken in it. One of my favorite places in the South Bay.
Pho Y #1: [San Jose] Very good southern-style (more strongly flavored with star anise, cinnamon, etc) beef pho.
Vung Tau: [San Jose] Fairly upscale Vietnamese in San Jose, but the food doesn't seem dumbed down at all. Apparently, dishes described as "caramelized" can be too sweet (my one data point agrees), so avoid those, but otherwise most menu items are good.
Bun Bo Hue An Nam:
[San Jose, 2 locations] Specializes in bun bo hue (duh), a Vietnamese
noodle soup that's generally spicier and more... rustic and
adventurous... than pho. I'm no expert here, but give it a try.
Falafel Drive-In: [San Jose] Convenient off of 880. Very tasty falafel though the pita sandwiches to tend to fall apart, so it's not exactly eat-in-the-car food. Lots of positive comments about the banana shakes as well.
Zeni Ethiopian: [San Jose] Lots of people rave about this place and it's pretty busy, but I was slightly underwhelmed. Dishes were somewhat hit-or-miss. A decent fraction of the people looked like they were from East Africa though, so maybe I'm the one out of step.
99 Chicken: [Santa Clara] Korean fried chicken. I really like it, but get the chicken with the sauce on the side otherwise it loses its crispy appeal.
Han Sung: [Santa Clara] My favorite Korean BBQ place. Uses real hardwood charcoal instead of gas. Good panchan.
Choi's Kitchen: [Santa Clara] Good Korean. The seafood pancake (haemul pajeon) is probably the best I've ever had, beating out longtime #1 favorite from (sadly now defunct) Sa Rit Gol in LA.
San Jose Tofu: [San Jose, beside Gombei] Not a restaurant. Freshly made tofu and tofu products. Pick up some when you're in Japantown.
Amber India: [Multiple locations - original in Mountain View] Upscale northern Indian cuisine.
Madras Cafe: [Sunnyvale] Tasty dosa.
Sakoon: [Mountain View] Upscale Indian.
Madhuban:
[Sunnyvale] Indian. Nicer than a normal place, but serving traditional
dishes. I think it's my new favorite Indian place. Almost everything
was excellent. One quibble is that the naan were not great. I might try
roti or chipathi next time instead.
Real Ice Cream: [Santa Clara] Really interesting Indian ice cream and kulfi. Some really good, exotic flavors. A bit tough to find as it's tucked behind and not so obvious from the street.
Slice of New York: [San Jose] Decent NY style pizza. Has slices and whole pies. Open fairly late if you're on your way home from SJC.
Pizza Bocca Lupo: [San Jose] Napoletana pizza. Looks like the real deal.
Blueline Pizza: [Campbell] From the same people as Little Star in SF/Berkeley, but different name. My favorite deep dish pizza anywhere. Waaaaaay better than Zachary's, and even better than the big-name Chicago joints (Uno, etc.). You can even get half-baked and finish the baking at home. Call ahead to streamline the process.
Juquilita Oaxaqueno: [San Jose] Nice place to find otherwise elusive Oaxacan dishes.
Bakery Mexico: [San Jose] Outstanding tortas. Large, cheap and delicious. Better than any I've had, save one stand by the UNAM metro station in Distrito Federal (a.k.a. Mexico City).
Dio Deka: [Los Gatos] Greek, nominally. I'd call it more of a chophouse with Greek tendencies. Pricey and, I don't think worth it. But great if relatives are coming and need something just slightly different but not at all challenging.
Manresa: [Los Gatos] Its reputation is as one of the best restaurants in the world (made the World Top 50 list by San Pellegrino). Michelin two stars as well. I don't find it to be worth the money, but others would argue vehemently against this view.
In case you need someplace to eat near SFO but it's after 10 pm.
Ajisen Ramen: [San Mateo] Japanese chain. During regular hours there are much better options, but it's not bad.
Izakaya Mai: [San Mateo] Haven't tried, but some good reviews.
In-n-Out Burger: [Millbrae] My default and open the latest.
New Krung Thai and Original Krung Thai:
[San Jose] Related (?) Thai restaurants very close to each other.
Reported to be the best Thai in the South Bay. Any chance that it's
anywhere near as good as Lers Ros in SF?
Xanh: [Mountain View] Upscale Vietnamese.
Huong Lan: [San Jose; also a branch in Milpitas but might not be quite as good] Banh mi (Vietnamese sandwiches).
Taste Good Beijing: [Milpitas] Northern Chinese.
Liou's House: [Milpitas] Chinese/Taiwanese.
Shanghai Dumplings: [Saratoga] Xiao long bao.
Cooking Papa: [Santa Clara] Cantonese banquet style food. High on my list to check out.
Huchi Ju Hachi: [Saratoga] Cooked Japanese dishes.
Muracci's: [Los Altos] Improbably-named place well-known for Japanese curry dishes.
Jang Su Jang: [Santa Clara] Korean. Heard many good things about the food, and also that it's expensive (relatively speaking).
Ilbungee #1: [Santa Clara] A dive-ish contender for best Korean BBQ in the area? Check out the Yelp advice on locating it since apparently it's hard to find (unless you can read Korean).
Layang Layang: [San Jose; also Milpitas] Malaysian. I've heard good things about it. They have all sorts of my favorite dishes like roti canai, kangkung belacan, Hainanese chicken and laksa (which they call Kari Mee). Also have Assam Laksa. Now I'm dying to go.
Tirupathi Bhimas: [Milpitas] Indian.
Saravana Bhavan: [Sunnyvale] Southern Indian.
Rose Market: [Saratoga] Persian kabobs.
Dish Dash: [Sunnyvale] Middle eastern. Heard many good things.
Walia: [San Jose] Ethiopian. I hear very good things.
Tu Mero Mole: [San Jose] Mexican - I hear good things about regional specialties like cabrito (goat), mole poblano and cochinita pibil
Naglee Park Garage: [San Jose] American.
Napoletana Pizzeria:
[Mountain View] Potential contender for best pizza in South Bay. One
report has it a notch below the best in SF and Berkeley/Oakland, but
it's much closer.
Village Pub: [Woodside] Upscale American.
La Strada: [Palo Alto] Italian with a reputation for excellent pastas and wood-fired pizzas.
Alexander's: [Cupertino] High end steak house with a few Asian influences. If you want really expensive wagyu (Japanese beef - Kobe beef is just one grade, and far from the highest grade) steak, this is the place to go.
Below are a few discussions from Chowhound that are worth looking through for suggestions. The key to Chowhound is to find people who you think are trustworthy and knowledgable and weight their posts more strongly. Key figures for me in the South Bay include the incomparable Melanie Wong, who seems to know a lot about almost every kind of food and "K K", who really knows his Chinese food.
Indian (South Bay and beyond)