The secret for choosing a type face is adhereing to the principle: The alphabet is a skeleton and a type face is a costume. The costume must fit the occasion.
Bob Trogman

Understated, contemporary, classic. That’s a tall order — particularly in trying to marry the last two. These might apply:

FF Absara Sans and Serif
Cronos
Relato Sans and Serif
Freight Sans and Serif
Fresco Sans and Serif

FF Quadraat (and Sans)

Thanks for the suggestions. I like Freight and Absara the best but I think Freight is gonna be the winner

If it is reallyl an “upscale” cafe - then, in my opinion, Frieght is to - pedestrian (freightish a word?)

Upscale should be something “classy” like a Carlton
http://www.myfonts.com/search?search%5Btext%5D=carlton

or an Egmont
http://www.myfonts.com/search?search%5Btext%5D=egmont

but then again, it means what kind of “upscale” — is this catering to the “in” crowd of the day? Is it catering to the money that is out there? What type of fare? What price range? Who are they trying to attract.

Ah, so many questions go into play before one picks out what would best marry the “product”....

P.S. If it is just for the menu - I’d try to find a serif font that had a bold and an italic counterpart. I keep redesigning menus here, because the original designers didn’t take into consideration - the 1) lighting of the restaurant and 2) the eyes of the customers.

I just did an “upscale” seafood restaurant myself - they owners insisted on Caslon Antique for all their menu choices - but we gave the customers - Caslon Book for reading purposes...

Good luck with the menu. There is more work involved then most are aware. Especially when you are all finished and the Chef says, “wait a minute...”

P.P.S. You may want to show an example of the restaurant’s logo - because you’ll want a face that compliments... (or is that complements in this case?)