Shop bought sandwiches are by and large pretty awful with or without mayo. I remember when I was much younger I would go the bakers nearest to my workplace and ask for whatever I wanted on a sandwich, I believe some still do this, and they would take an oven bottom - a large freshly baked bap - butter it and put the filling inside, no mayo, it wasn’t a option back then. Was delicious. And when we visited New York several years ago, wherever we went for lunch sandwiches would be made freshly for you with loads of choices of bread, sadly they would use mayo rather than butter but am sure the sandwiches were better than the awful shop bought ones on offer over here.