This is what I do:
1) Don't buy from them if they don't accept bitcoin. When I have extra time, I'll let their manager know that if they accepted the easiest non-paper payment method on earth to accept... they would not only get me as a customer, but a very loyal customer. When it is companies like a coffee place, i'll tell them why I buy Starbucks coffee instead of their coffee: simply because I can buy a gift card for Starbucks with bitcoin.
2) When EVER I tip someone, it's in bitcoin. Don't have a bitcoin wallet on your smart phone, eh? Then sorry... no tip for you. Actually, I've tipped easily over 100 individuals. I've only had 2 people refuse a tip--1 person who's phone died and they wouldn't accept a paper wallet, and another person who rudely tried to educate me on how to write a tip amount onto a merchant receipt. If it were worth my time, I would've showed them how to download apps on their phone
I mean that's great and all to try and promote Bitcoin that way, I mean I'm still working through an internship program at the moment and work in the food/service industry still and would love to get a tip and talk about Bitcoin with someone like yourself, but fuck... Just because they don't feel like learning something when they are probably extremely busy and just want the convenience in receiving a normal tip is to be expected, shouldn't be considered "rude". They work hard, and litterally served you.. Why should you deny them tip when they are probably working for way under minimum wage?
If I were you I would still offer the Bitcoin tips and promote them to getting a wallet, but if they don't want it, just say ok and move on to giving them that dirty fiat. You're essentially trying to tell them that fiat is no good and they should accept your digital gold, and it would make more of a statement if you tipped them more in fiat than you would have in Bitcoin.
I would also suggest making a little business card or flyer to leave business or people who serve you, so when they do have a chance to sit down and relax after a hard days work, they might get really interested in what you had to say after all, and start reading what you left them. You don't have to completely stiff them a tip, now that's "rude".