We went to The Warehouse on King Street in Old Town Alexandria for brunch Sunday and were very pleased. We were seated by the window which gave us a great view of the passersby and the snow flurries. They serve excellent seafood with a New Orleans slant, have elegant seating in a pretty space (particularly for a place called "The Warehouse"!), offered prompt service, not to mention very tasty champagne with strawberries. :) There were a few classic breakfast style meals (french toast, eggs, etc.) for those not inclined toward seafood. I gotta tell ya, though, the shrimp and crawfish beignets were quite decadent and the pecan crusted talapia with balsamic glaze over mixed greens was excellent. Not on the cheap side but we've paid more and not been as happy other places.
So... for brunch, since this is our only experience, I'd say out of possible 30/category:
Vegetarian Options: 15
Food: 26 (it would be 27 if the bread had been warm)