"Deli" is short for "Delicatessen," which originally referred to fine foods (delicacies) and/or the store that sold them: the corner shop that specialized in imported meats & cheeses, for example.
These days a deli (in the U.S. anyway) is typically a small local market that makes & sells sandwiches. Unlike a convenience store (7-11 or a gas station market) a deli prepares & sells food. Unlike a chain restaurant (Subway), delis are often family owned or local to the area.
Delis often sell other necessities too like milk, eggs, snacks, candy, and newspapers/magazines, which is why the person in your quote went there looking for the Sunday Times. You'll also see "the deli counter" in larger grocery stores where you can buy meats, cheese, sandwiches, and other prepared foods like pasta & salads, but you wouldn't call the whole large store a "deli."