it's still a request that would not plausibly be granted unless the asker has great power or status over the askee,

Have you ever studied linguistic pragmatics? I would highly recommend you read up on Brown and Levinson's concepts of politeness. They talk about there being three factors in interaction that determine your level of politeness: social distance, power difference, and weight of request. In the sandwich example you come across as rude because, as you say, you're acting as though the other person is lower power than you. If they were your close friend you could maybe get away with that sort of behaviour, especially since you're not asking for much, but it's still pretty chancy. Better to add some extra politeness and grovel rather than ask for that sort of thing.

(of course, if you were sufficiently more powerful, you could get away with ordering a sandwich, and you would still probably be rude, only justifiably so ;)