Forgot to mention Tivoli, in Rosslyn just across from Georgetown and 4 or five floors straight up from the Rosslyn Metro station. Fantastic Italian-ish menu, wine selection is most excellent and not to too terribly overpriced. But the better entrees are typically in the $30 range...But at least they serve the meal in the proper order (with the caesar salad late in the meal).

It is my parent's favorite (they are on first name basis w/matire'd).

If that's too pricey and you're in Rosslyn, try Tom Sarris' New Orleans just down the street...