Big multi-nationals are difficult because obviously all their policy is dictated to them by headquarters, but tradesmen and small, independent retailers are generally pretty easy here. Any time I'm hiring any tradesman to have work done on my house, land, car, etc, after they've quoted me I always ask - "Do you accept Bitcoin?". If they don't want to, fine, but it at least lets them know the demand is out there. Farmer's markets, public markets, street vendors, food stands and the like are all easy to convince as well.