You're correct about Recital 43 not applying to the contract case - what it does is establish that the main
alternative to "necessary for the performance of a contract" isn't there in the sandwich example.
The core of the regulation is Article 6(1), which is basically a big old "or" statement; you have to fulfill one of the conditions listed in order to lawfully process data. [1]
a) is consent, as explained in Recital 43 and clarified in other places. The sandwich vendor clearly doesn't have that, since they've conditioned the service on the delivery of data.
b) is "necessary for the performance of a contract". This is the option on which your free-lunch-giver is leaning. "Necessary" is not well-defined in the EU-wide regulation, but judging by the UK example I linked (the ICO), implementing Member State agencies are going to take a narrow view of "necessary" - as in where it's impossible for the controller to perform the contract without processing the data. By contrast, Recital 43 uses "dependent" to refer to the service provider establishing conditions. This also fits well with the usage of the word in the other tines of the Article 6(1) fork. (c: "necessary for the compliance with a legal obligation", d: "necessary to protect the vital interests of [actual people]", e: "necessary for the performance of a task carried out in the public interest or in in the exercise of official authority" [2]). This interpretation is also, in practical terms, the only one that makes sense, as otherwise the consent option (a) would be redundant.
[1] The most friendly version of the English-language full text I can find is here: https://eur-lex.europa.eu/legal-content/EN/TXT/HTML/?uri=CEL...)
[2] This interesting clause stemming from an even more interesting feature of GDPR: it applies to government agencies. Meaning the regulation needs specific language to specify that yes, the Ministry of Transportation in your country is allowed to use your vehicle registration information as part of its road planning process.