I’ll second (or third) Tim’s Cajun Kitchen. Another hole in the wall place is Jamo’s Cafe on Jordan Lane. They have Mediterranean/greek style food (gyros, kafta, falafel, hummus, etc.) and coffee drinks.
If you want something more upscale try Edo Japanese Restaurant.
As for Barbecue I like the Golden Rule in Madison. They have more than just typical BBQ fare, including fried green tomatoes, which I get practically every time I go.