HELP! Looking for restaurants in the Palo Alto area
My husband just moved out to Palo Alto for work from NYC. I visit frequently, but we never know where to eat (he works a ton, so doesn't have time to check places out... plus he's not much of a foodie). The only things he's found are Whole Foods, In-n-Out and Evvia.
Would love some suggestions for
... and anything else you think is relevant! Price points are less important than good food. Thank you so much (I'm a chowhound newbie and have already learned so much from just going thru the boards)!
this probably should go on a separate board, but this past weekend, my husband and i took my mother on a road trip up the coast to Point Reyes/Marshall. our first stop was the Tomales Bay Oyster Company, where we knocked out 50 small (much larger than i expected -- double the size of kumamotos) oysters. my husband was the designated shucker, since he doesn't eat oysters. we had about 35 raw and 15 on the bbq, and i truly don't know which were better, as they were so fresh, briny and delicious. i had never had oysters on the grill before, and when taken off at the right moment, the warm juices and the perfectly tender oyster are such a wonderful combination!
we then drove up the street to the Marshall Store to try the clam chowder and chicken tamales (finally something that my husband could eat). i personally found the chowder a bit too herby, but the huge chunks of clam were delicious and not chewy at all. my husband, who is a huge tamale fan, found the chicken to be dry but the overall tamale to be excellent. they also had Dungeness crab that day which we ordered (cleaned and cracked). my mom was in heaven, and i smelled like crab the entire rest of the day, but it was completely worth it (and worth the extra $4 to have it cleaned and cracked, as it made the eating so much easier!).
we then drove over the mountain into Napa where we sampled Miner Vineyards (unfortunately we missed the tour, but really enjoyed the wine and our 30 minutes there) and Cliff Lede Vineyard (which we thoroughly enjoyed -- we ended up drinking most of our sparkling wine purchases yesterday ringing in the new year!), and then headed into the quaint town of Yountville for dinner.
i wanted to go to Ad Hoc, but when I called a few days prior while organizing this trip, they were fully committed. but i thought i would try again while we were there, especially b/c the menu was something my husband wouldn't be picky about, but it was only 5:15p and the only available time they had was 7:30pm (btw, Ad Hoc now takes reservations, which is a change from when they opened).
We tried Bouchon (fully committed) and passed Bistro Jeanty (my husband isn't a huge fan of French bistro), and finally settled into Redd, who had a full dining room, but had availability at a small table in the bar area.
i was very impressed with Redd... the service and food were impeccable. We started with the risotto with Maine lobster and white truffle oil, hamachi sashimi and a special, Nantucket Bay scallops with potato gnocchi over a butternut squash puree. my mom claims to dislike scallops, but she was amazed at how sweet and tender the scallops in my dish were. the hamachi melted in your mouth. and the risotto was perfectly toothsome and infused with enough white truffle without being overpowering.
as for the rest of our meal, we had a special sweetbread appetizer, a special pasta of homemade fettucine with veal and ricotta meatballs, and the new york steak/short rib dish. my sweetbreads were delicious, except that the olive oil potatoes which it was served with were too heavy. the pasta was amazing but did have a bit too much white truffle oil for my husband (he felt it overpowered the dish). the steak was amazing, and perfectly cooked to medium rare. the braised short ribs that accompanied the steak reminded us of Korean kalbi jjim (braised short ribs), but had not been trimmed of enough fat so tasted almost greasy with each bite.
finally we ordered the chocolate souffle, which was slightly overcooked, but tasty nonetheless. i HIGHLY RECOMMEND Redd, and look forward to traveling back to wine country to try it again!!
i'm returning home to NYC tonight, but am back in SF/Palo Alto in just 3 days (to celebrate Gary Danko's 50th birthday!!) so am looking forward to reporting more.
A few of my faves:
Joanie's: French-owned, speedy service (it's popular, too: get there earlyish for breakfast/lunch on weekends, but there's a great used bookstore a few doors down - Know Knew Books - to help pass the time). The oatmeal also sells out relatively early, too, cuz it's GREAT! Omelets, naturally, excellent. Waffles also. Salads are generous and never overdressed. Atmosphere: casual but not sloppy, photos of France to inspire you and as per usual in Palo Alto, a chance to hear several languages spoken. Something for all generations here. Prices: reasonable.
Junoon: Newly opened in downtown PA (University at High, Junoon ( Indian modern/fusion/whatever) has risen quickly to top 10 lists of Bay Area restaurant critics (restaurant's website has link to an Esquire mag piece that puts it on top 20 list of new restaurants in the U.S.) and with good reason. Its prices mean it's not a place for regular meals (unless money is not an object), but every meal is memorable.
Pluto's: Great bargain for salads: pick your greens, pick 10 add-ins - walk away with a whole-meal size salad for about $6. It's semi-self service (you stand in line with a menu, hand it to a server who makes your meal (kitchen mostly visible), you go find yourself a table. Great roasted turkey (plus mash and gravy) for cold weather. This is another University Avenue place for a quick healthy meal for a reasonable price - but it is more lunchy than dinner fare.
Palo Alto Sol (on California Avenue): previously mentioned in these posts - I concur: good food, quick service, reasonable prices. I like the broiled camarones cilantro.
Coupa: yes, terrific coffee. Single-estate Venezuelan. Hand-made chocolates of unusual combos: try the one with chevre.
Caffe del Doge: Check out the specialty drinks made with chocolate. Another strong point: pastries.
Crepes: Bistro Maxine (near Coupa on Ramona Street). Made like they do in France. Just a few tables with some on sidewalk, so it's "intime." Cafe au lait served in drinking bowl - again, a la mode Francais.
Thanks again to everyone for posting suggestions. We've been eating in both SF (I have some family in the city) and Palo Alto. We tried Limon in the Mission, which was packed, but the service was terrible, and the food was just so-so. (We had two ceviches (ceviche Limon and a creme ceviche) both of which were good, very typical Peruvian, and the lomo saltado, which was greasy and not as good as I've had at some other less expensive Peruvian places back in NY and a mixed seafood dish with rococo (?) cream sauce.)
We also tried Nola in Palo Alto, which was edible. The crab cakes were delish, very crabby, quite good. The fried calamari was decent, tasty spicy dipping sauce. The fish tacos were OK (nothing remarkable), the jambalaya was terrible (this coming from my husband, who doesn't love food, but lived in New Orleans for a few years, and LOVES their local food), the beignets weren't greasy. The black beans that accompanied the fish tacos were delicious. The service was TERRIBLE.
We just got take-out from Darbar (after being stuck in traffic, I couldn't motivate to Amber India). Perhaps we ordered the wrong dishes? We ordered the beef samosas (raisins inside? gross), chicken korma (generally our favorite, but this version was sweet... and gross), and daal makhani (off the menu, but generally our favorite daal, and this was probably the best daal makhani we've ever had). The naan was unremarkable, but it may be because we had take-out. The daal side that came with the dishes was pretty good as well.
We're looking forward to trying Amber India after Darbar was so disappointing. Does anyone recommend any dishes at Darbar? Same question for Amber India... (before we go). Also has anyone tried Hydrabad Cafe on University?
We're going to La Ciccia in SF tomorrow night and then up to Marshall and back thru Napa on Saturday, so will report back again. Thanks again!!
Glad to hear you've had some hits, sorry about the misses. Amber India is known for their Butter Chicken and Mirch Ka Gosht (lamb with peppercorns and chiles.) Be warned that the lamb is REALLY hot, it doesn't hit you at first but as you eat, it builds up and before you know it you're on fire. Every time I have it, I have to stick my head out the window on the drive home, a habit which has earned me the nickname "pooch" with the witnesses. As far as the rest of the menu goes, we've never had anything less than "great," so order whatever looks good and post back! :)
Nola - yeah, that sounds right. Jambalaya is just tough outside of NO (just try finding dirty rice), and the food at Nola isn't *great*.
Darbar - I'm surprised as your definition of "gross", as I like raisins in my samosas, and in any case consider it a reasonable variation (one of my favorite food experiences being "somosa masala" at a truckstop outside bangalore - indians don't seem to treat somosas as a purist food). Good nan always gets mushy when taken-out, and is not Darbar's strength anyway. I often get the vindaloo there, and tend to order spicy, usually lamb-based. I see Darbar as a good everyday restaurant, not much more. When I really want to eat indian, I've got a place in San Jose I like that's much more down home.
Amber's food is a bit more refined, for better or worse, and may be your cup of tea. I find it a little prissy - I like my indian bold and gut-wrenching - but do think the tastes are clear, and the ingrediants fresh.
Hydrabad Cafe opened somewhat recently (in the last year, anyway), and I haven't tried it. Please post.
What is your definition of "terrible service"? (Given that you've rated both your dining-in experiences as "terrible".) Curious. For me, all I really expect from places in this category is prompt menu drop-off, ordering within 5 minutes of when I'm ready, and being able to get a check without waving my arms wildly. "Terrible" means the order was significantly wrong, that I was personally insulted (story: upon finding a large shard of glass in salsa, I was accused of having planted it and told the the cops would be called if I didn't shut up), or that I had to wait more than 15 minutes in any of the three states (menu, order, bill).
Palo Alto should not, in any circumstances, be considered a chowhound hotspot. Most people will tell you simply not to eat there. "Ethnic" food is average at best, overpriced at worst; high end food is long on design and short on execution. The only place in PA that I think is actually excellent is Tamarine - although I've been there exactly once, and from other reviews, happened to order well (my rule is three excellent meals makes a resturant).
There's a lot of places mentioned on the board that I think are simply OK (like del Sol on California). The only PA place that I've been daydreaming of is the Tofu Soup place on El Camino near San Antonio - simply because I miss decent Korean so much. It's not really in the league of the Korean Oakland places.
thanks for the tips. i do have a tendency to call anything remotely bad the WORST, etc. but i also feel that waiting 15 min to order, not having someone refill your waters or check on your empty wine glass for over 20 min, not checking to see how you're doing after receiving meals, etc. is terrible service. especially when it's not as though Nola or Limon were cheap.
also i'm looking forward to trying the Tofu spot on El Camino (i hope it's the one next to Fuki Sushi) -- my mom never cooks anymore, so we rarely get to eat Korean these days.
i personally do not enjoy raisins in my savory foods, and when we make samosas with my girlfriend's family from hydrabad, they have never included raisins, nor have any from any of the indian places in NYC that we frequent. but to each his own.... it was new to me... now i know to ask :)
i would love to know the indian spot in San Jose that you like -- it's not too far from PA and i'm flying in and out of San Jose on my next trip out.
thanks for the recs!!
Tofu House-It's definitely the one next to Fuki Sushi. It has no atmosphere, small selection of decent panchan, but the tofu soup is pretty good! Also good service- no alcohol. (The Bulgolgi is horrible and the Bibimbap looks mediocre though).
There's some really good Korean BBQ up in the city as well so you don't have to go all the way to Oakland. I like Brothers, on 5th and Geary, but there are many other opinions out there.
Just for the record and for the sake of having a balanced viewpoint, Tofu House is really not that good. It's ok for the area, but hopefully not the best in the peninsula and certainly wouldn't hold a candle to some of the better Korean soondobu places in LA's ktown. The flavors are just not deep enough. It's quick and dirty comfort food.
So anyone looking for *amazing* soon tofu should be forewarned that Tofu House on El Camino serves up hot, tasty fare at relatively decent prices, but don't set your expectations too high if you've had really good soondobu before.
Ok. My indian place is Mayuri. Here's a long post that drew no responses, and is fairly accurate.
In this context, I'll say that the dosas are straight outta madras, the ever-bizzare california invention of Chicken 65 never fails to please, and I continue to eye the Phaal and Vindaloo, given that the daal for the dosas is about an 8 on my personal spice meter (8 is good!). The nan is only above average, and they make a kick-ass salty lassi. Portions are on the large side. For about $20 each we end up with a large grocery bag of left overs.
I've never had the Weds. buffet. It's recommended, for sure.
The service is uneven. It's an indian resturant, for all that implies. Lots of staff, sometimes right at your elbow, sometimes lounging pretending not to serve you. They'll bring a water jug to your table --- usually. The tables are plastic-topped, and the interior looks like a 70's pancake house. Utensils tend to be clean. This ain't fine dining.
I usually go on a weekend, and they always have an indian party (wedding reception? birthday? who knows) at the function room next door that's as big as the restaurant. Lends a nice atmosphere. There's usually a few large indian families, and a scattering of small groups of non-indian people.
This area of El Camino used to be chock-a-block with similar indian places, but most have closed --- and turned into Korean places. I'd love to see a thread on Santa Clara Korean. My girlfriend laments various places, and laments Mayuri as not-quite-as-good, but I don't care - Mayuri is fine by me.
A few more thoughts:
+ Get some pastries at the Prolific Oven (I'm partial to the carrot cake there, its one of the things I miss most about Palo Alto, other than the weather).
+ Go to Redwood City (El Camino Real/Middlefield, near downtown) for great Mexican. My favorites are La Casita Chillanga (great tortas, and also amazing barbacoa on the weekends) or La Pachanga (on Middefield) for a more sit-down meal. Neither one is fancy, but both are cheap and filling.
+ There's also good Turkish food in the area. There's New Kapodokia in RWC, and two newer places: one in Menlo Park (right on ECR) and one in Mountain View on Castro. The one in Mountain View (I'm blanking on the name) is quite good.
I'm glad nutmeg added Marche. I have had really nice food there - just not cheap.
So when you are ready to venture out, ask on the board about Asian food either up in San Mateo/Foster City/San Bruno or down in Mt. View/Sunnyvale/Santa Clara
Now, all you need to know is where to go for a pedicure:).
Natalie's Nail on El Camino....haha
I couldn’t resist adding to the list. Here are my favorites, several already mentioned...
• Zibbbibo (Kipling) – Cal/Med cuisine, good bar, nice wine menu, nice brunch.
• Quattro (4 Season Hotel) – Great bar, yummy aps, nice brunch
• Bistro Elan (California Ave) – Nice French bistro.
• Marché (Menlo Park, Santa Cruz) – upscale. One of the best French restaurants on the Peninsula.
• Keygetsu (Menlo Park, Sand Hill Road/Sharon Heights Shopping Center) – Outstanding sushi. (Hands down THE best.) Get the kaiseki with sake pairing.
• Brix (Menlo Park, El Camino) – Great basic burgers and fries.
• Cool Café (Stanford Univ, Cantor Center) – Great lunch spot in Rodin Sculpture Garden esp on a sunny day. Same owners as Flea St. Café in Menlo Park.
• Tamarine (University Ave) – Excellent upscale Vietnamese. Nice bar.
• Amber India (El Camino, Mountain View) – Fantastic Indian.
• Coupa Café (Ramona St.) – Great coffee. Nice Panini. Great salads. (free wireless)
• Los Altos Grill (3rd St, Los Altos) – LOVE the grilled artichokes. Millionaires steak is the best!
• Grill on the Alley (Fairmont Hotel, San Jose) – Fantastic rib-eyes. Delicious creamed spinach. Great shrimp cocktail. Excellent dirty martinis. Feels like NY.
• For dim sum... Nothing in PA. Make the trip to SF. Ton Kiang (Geary Street) or Koi Palace (Daly City just South of SF) are my favorites. Alternatively, you can drive to Milpitas to Mayflower for dim sum.
PS - And speaking of steak, since you live here now and will presumably be cooking... MUST go to Schaub’s meat market at Stanford Shopping Center. Your mission is to order up a local legend known as "Fred's steak." Don't be alarmed that the meat is strangely black --- the extra double super secret marinade makes it so. And if you don't have what it takes to cook a full tri-tip, pick up some Fred's steak burgers. (Paling by comparison, but they'll still satisfy that urge.)
-sushi: Homma's Brown Rice Sushi... hole-in-the-wall just off California Ave but they get a lot of business and it's really really fresh
-dim sum: hands down, Joy Luck Place in Cupertino Village. best dim sum I've had, nor and so cal combined
-Indian: hands down, Amber India on El Camino. since I left PA, haven't found anything that can compare...
-brunch: I love Cafe Borrone's on El Camino at Santa Clara, next to Kaplan's books. Adorable coffee shop with great food and excellent atmosphere
-French bistro: I miss Cafe Brioche SO MUCH!!
-seafood: ?? go to SF
-burgers: in n' out is my fave
Reading all these names again in everyone's posts makes me all teary... You practically can't go wrong around there!
i loved their openface avocado-shrimp-cheddar tartine and had a lovely tarte tatin there too. i never really got into Joanie's next door... i found cafe brioche to be much more charming (alas, they have taken down their indoor umbrellas, which gave the place such a unique feel)
... it seems like i went everywhere in the 4 years i was up there... and the places i miss terribly and could never replace are:
borrone's, amber india, evvia, and a capuccino from coupa cafe
and Nora's has a shrimp dish that is very tasty and comes with the shrimp hanging on a rack. Cute!
I also rec. Coupa Cafe (Ramona St) - Get the spicy hot chocolate, and sopas.
and we often end up at Peninsula Creamery. We share a coffee malt and eat a strange mix of stuff -- fried calimari and turkey burgers or like that...
When I went to 'I Tapas' last week, I mentioned to my girlfriend that, between one thing and another, I was getting used to Palo Alto, and had been to all but about 25 restaurants on greater university ave. She proved me wrong - we found that the number was about 50 - and counted nearly 150 just in that area alone. Like Prolific Oven - I had just never wandered down that street.
So what's your real question? Pull up Yelp and Citysearch, and dig in!
-steakhouse -- Sundance, as noted.
-sushi -- I haven't settled on a favorite. I often end up at Tokyo Subway for Japanese simply because they do a very nice teppanaki (their sushi blows), or Miyaki because it's fast, cheap and out of control. I miss Higashi West, which was my standard. Hama's brown rice is great, but you have to be up for the experience.
-dim sum -- Read the threads about millbrea and san mateo for endless discussions of XLB and similar. In comparison, there is no dim sum in Palo Alto.
-Indian -- Amber's great, but I end up at Darbar on Lytton. It's spicy there, and more casual. If I'm up for a drive, I've got a favorite spot called "Mayuri" in San Jose for South Indian (Chicken 65 and Dosas!), or good old Sue's in Mt View (partially for nostalgia - my first vindaloo!)
-brunch -- I don't really do brunch.
-French bistro -- No recommendation - they all seem good.
-seafood -- Seafood is no longer a category for me. If by "seafood" you mean a place like Scott's, I just don't go. Instead, I'll aim for a particular type of restaurant that specializes in fish, like I might think of I Tapas' Crispy Smelts or a great thai fish curry or Khana Peena had a great fish tandoori one evening or that salmon I had at Boulevard.
-burgers -- I did The Counter once, and was VERY unimpressed by the quality->price tradeoff. I am not used to spending $80 for burgers for two. Oasis burgers are standard and the beer selection is poor - you have to like that atmosphere (similar to Dutch Goose). When I'm in a beer n burgers mood, I head up to City Pub in RC because they have Lagunitas IPA and a tolerable burger. I end up at Peninsula Creamery when I'm in the diner/burger mood, mostly for the shakes, but generally despair finding a good burger 'round here. (There was a LONG burger thread recently centering on SF/EB) I'd rather get some fresh $2/lb molida at Mi Rancho on Willow, fold in some garlic, grab some rosmary, and turn up the grill.
You didn't mention Pizza. There's a huge thread about Peninsula pizza, and I won't weigh in. I am fond of Pizza My Heart's BBQ chicken, but wouldn't *recommend* it.
Here's a short list of what I'd try first:
Tamerine - I need to go there a second time, but as of first taste, it really is "all that" - the only place in PA I feel that way about (Zibbibo, Straits are pretenders and I haven't tried several of the others like Lavande and F&A and Niebaum Coppola).
NOLA - I realize the atmosphere is a construct, but new orleans itself is a construct. The food is far better than it needs to be, and the bar kicks ass.
Darbar - casual, down-home techie indian. Nothing wrong with that.
Tofu Whatever - on El Camino near the Los Altos line with the funny face. Triple minus on the atmosphere, triple plus on the Korean Soup. Great cold night kind of place, and reminds me of all the Korean places I miss from Oakland.
3 Seasons / I Tapas - 3 Seasons has been a standby, mostly because my eating partner prefers small plates, the mussels are good, and they have a bar. However, we will likely shift to I Tapas when we're in that mood, because the food at 3 Seasons is a bit dull.
Mi Rancho and La Hacienda - slightly closer than the Redwood City enclave of mexican, these guys both put out a decent burrito, although I could quibble with both on a number of counts. Yesterday I discovered Mi Rancho's spicy chicken filling, which I've never seen before and is most tasty.
A short drive, standards are Chef Liu in Mt View for Chinese (they have a touch of dim sum and are closer than Millbrea), and Amerin Thai in MV for Thai (recently supplanting Thai Time in San Carlos), and Med Delight in SC for schwarma (although they've changed owners - there are now *men* behind the counter, where the place was always run by women. I'm watching you guys!)
Here are some of my faves:
Sushi House (University Ave) - Small place - great sushi.
Gombei (El Camino, Menlo Park) - Japanese homestyle cooking but not sushi.
Osteria (Corner of Hamilton and Ramona) - great Italian place. You definitely need a reservation here but the food is always great.
St. Michael's Alley (Emerson Ave) - Great local place with fresh ingredients - more along the lines of California cuisine. Great date place and brunch.
Tamarine (University Ave) - Vietnamese fusion. Very popular.
Zibbibo (Kipling St) - California/Mediterranean. I like the side dishes here.
Coupa Cafe (Ramona St) - Great coffee here.
Empire Tap Room (Emerson St) - If it were warmer outside, this is a great restaurant because of the outdoor patio. They have great crab cakes.
Hobee's (Town and Country) - Great coffee cake and "healthy" breakfasts here.
Homma's Brown Rice Sushi (off of California) - this place is in a pink building in an alley off of California. Definitely v. good sushi.
Pluto's (University Ave) - I saw Chelsea Clinton here once. Good comfort food.
Cook's Seafood (El Camino, Menlo Park) - It isn't fancy but they have great fresh fish. or you could pop into their store and buy it to take home.
Peninsula Creamery (Hamilton & Emerson) - I really like this place for a diner time of burgers and milkshakes.
University Ave, California Ave and downtown Mountain View all lots of restaurants. Just wander around and you're sure to find something great.
In addition to those places listed:
Sushi: Sushi House in Palo Alto Town and Country. Small, casual, home style food.
Burger's: Oasis in Menlo Park (carve your names in the table) Juicy burgers, and grilled sandwiches. 1 mile away from Stanford University, Stanford forbid the sale of alcohol within 1 mile of the campus, this was one of several beer gardens outside the exclusion zone. Alpine Beer Gardens is the other remaining (?).
Deep Fried Seafood, Seafood Salads: Cook's Seafood, Menlo Park ("meaty" halibut featured as "fish and chips", chips are "steak fries". Both local fish stew, "chiopino" and white clam chowder)
California Cuisine: Flea Street Cafe, Menlo Park.
Bella's, Redwood City, Seaport Blvd. Port of Redwood City, formally Clark's. good place: food, service, venue are all good, not excellent not ok, always above average, a place to go for the view, see another part of Redwood City; RWC has a working harbor, see a $800m business campus at the end of Seaport Blvd.
Road house Steak House: Cat's in Los Gatos, need to be an above average driver to be comfortable crossing the highway on the way home. Live music on some nights, steaks, grilled chicken, bbq' ribs.
Would love some suggestions for
-steakhouse Sundance ... decent, but abit overpriced
-sushi Sushi-Ya, University Ave, excellent
-dim sum Nothing, Mings OK, try Joy Luck in San Mateo
-Indian Amber India in Mt View
-brunch Joanies or Cafe Brioche on CA Ave or
Dinah's Poolside Restaurant
-French bistro Cafe Brioche or Bistro Elan on California
-burgers You might try The Counter on CA Ave ...
decent burgers, great concept
I like Trattoria Buon Gusto in Menlo Park for Italian. I also like Su Hong in Palo Alto for xiao long bao. For sushi, Naomi is probably best, on El Camino. For breakfast with coffee, Cafe Borrone. For American, i.e. burgers, steak, McArthur Park. For Mexican, go north a little bit and try the taquerias and mariscado places on Middlefield past 5th. I hear that Kaygetsu up in Sharon Heights is fantastic but have not been. For pizza? I like Applewood. For martinis? Spago's bar. For Indian, don't know now that Marigold closed.
Just University and wander. You might not get great food but you will get the vibe. Oh yeah, also to to California Ave and go to Bodega del Media(sp?) good Cuban and fun atmosphere. Also Tamarine or Three Seasons for fancy Vietnamese.
We may be the suburbs, but its not so bad down here.
Some of my faves in Palo Alto are:
-Bistro Elan--Cal/French bistro
-La Bodeguita del Medio (sp?)--Cal/cuban/tapas
-Cibo for burgers, this is an odd hotel diner-ish kind of place but the burgers are really good, can't really recommend anything else here
-Kaygetsu in Menlo Park for sushi/japanese, although it's quite expensive
-Tamarine--upscale fusion Vietnamese
-Mings is ok for dim sum, not great. There's really not a lot of choices in Palo Alto for dim sum
-Straits--upscale Singaporean, only go to this location. Don't ever go to its sister location in San Jose's Santana Row
I've yet to find a great seafood place in Palo Alto. Don't bother with the Fish Market restaurant.
Actually, I have to stick up a bit for the Fish Market, and recommend checking it out as long as you stay within its wheelhouse - straightforward grilled fish, buckets of steamed mussels, etc at reasonable prices. Steer clear of their attempts at haute cuisine, have a beer, and you'll be fine.
Also -- although it's not on the menu, you can order a (still huge!) half order of their cioppino, which is better than many preparations I've eaten in SF.