It's got some snap to it
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 comment ✣ by Tarvek hints that Jäger-sandwich construction may have truly impacted Europa's history. (Probably still filling in the craters..)
Ol' Man Death, a sandwich maker of some renown, is naturally familiar with all of these, possibly to his regret in some cases; his adventuresome tale is told in the short side-story Maxim Buys a Hat.
After sleep-building the Othar-Rescuing Clank on board Castle Wulfenbach, Agatha makes and eats ✣ a sandwich from components supplied by Gil.
During a brief break in the action in Castle Heterodyne, Gil eats ✣ 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.
While in England, Krosp engages ✣ in a sandwich-stealing spree with his fellow heroes. Unfortunately for him, Gil retaliates by lacing one of them with ghost pirate peppers.
In an airship on the way to Paris, Norville eats sandwiches ✣ 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.
During their Incredible Journey in the outskirts of the time-frozen Mechanicsburg, the previously-antagonistic Krosp and Norville bond ✣ over a feast of sandwiches they encounter.
When Martellus von Blitzengaard arrives at Mechanicsburg as well, Krosp greets him and serves ✣ him a fish-head which Tweedle seasons and makes into a sandwich.
Somewhat later, still just outside time-frozen Mechanicsburg, after another discussion between Krosp and Martellus, the cat goes off to do "terribly important things", accompanied by his counterpart, the Empress. Although doubtful Krosp really has anything important to do, she tags along as he steals "fishy pickles" and then joins Norville, who is making ✣ special cheesydog sandwiches. It turns out that the "pickles" are a vital accompaniment to (or possibly an ingredient in) Norville's sandwiches, which even the Empress has to admit are irresistibly delicious.