The concept of slapping assorted fillings between two slices of bread and chowing down on the resulting gestalt is known to the citizens of Agatha's Europa. In the Mechanicsburg area, along with more familiar chicken salad and beef tongue, snails and bats are on the menu often enough that they have all acquired their own "diner lingo" title: respectively, the Botched Construct, the Martian Princess, the Racing Trilobite and the Red Heterodyne. There's also the rather pricey kosher schlognwurst; perhaps it's just as well we haven't heard what its nickname is.
And that's what the normal(ish) humans eat, when Jägers come calling, you can add in literal greasetrap cheese and (raw) mystery meat, and even a Prince of Sturmhalten's Big Bet: one hat sandwich, to go! Indeed, an offhand by Tarvek hints that Jäger-sandwich construction may have truly impacted Europa's history. (Probably still filling in the craters..)
During a brief break in the action in Castle Heterodyne, Gil a sandwich offered to him by Zola, filled with some sort of crustacean; in Agatha H. and the Voice of the Castle, we are informed that it is a Deep Fried Crunchy Castle Crab, a Sparkily-enhanced species of louse. It is evidently quite delicious, but even Mechanicsburg citizens have their gastronomic standards, and so feed them to, yes, prisoners in the Castle and (eww) tourists.
In an airship on the way to Paris, Norville eats prepared by Gil. Norville is a one of Martellus's Knights of the Hunt, captured by and now working with Gil and Tarvek. Norville still hates Tarvek, but has formed a very high opinion of Gil, seemingly because of the sandwiches, which he enjoys tremendously. Tarvek later complains that Gil is using his sandwich recipe.