> Huh, I thought accepting legal tender was a federal rule, I guess not.

I think the key word is debt when bills state "for all debts, public and private." (And a couple more categories under the law. [0])

At the moment you're asking for the drink, you are not in debt to the coffee shop, they're setting a precondition on an exchange. [1] Now, you might have a case if they let you run up a tab...

[0] https://www.law.cornell.edu/uscode/text/31/5103

[1] Yes, there are a positive number of milliseconds where somebody owes somebody something, but pedantic software intuitions don't always apply to law, and overall that's a good thing.