You don't need a new cryptocurrency for that. Just lower your prices for people paying with BTC/ETH/... to adjust. (Doesn't solve the potentially bigger issue of insurance though, but I think that has to involve some third party)
You can definitely do that and the end cost for the consumer would be the same, but it would result in vastly different levels of consumer usage.
edit: On second thought, you are probably right. With the right wallet ui you could just provide a simple discount or cashback that covers the transaction fee + % cashback at the point of purchase that's covered by the recipient via a contract, or via rules that the recipient publishes.
1) It costs them money to use 2) No cashback
It would be interesting to test a cryptocurrency where the recipient payed the fee, and could optionally send cashback. I'm not exactly sure how this would work, but the incentive structure would more optimally aligned for everyone involved.