Idk. Where I live, it's very common. Almost every gas station does it, about half the restaurants, and yes every utility. 0 grocery stores though. The fee is at least 3%, and no card offers that level of cashback, though you might be able to do the equivalent of 5% with airline miles.

Cardholder agreements used to disallow CC surcharges, but I think such clauses were outlawed.