> I can't see how it should be alright to pay people differently based on their cost of living.

Insofar as local CoL correlates with race and potentially other protected characteristics (religion seems likely, for instance), there's a pretty good “disparate impact” argument that it would be presumptively illegal if challenged under US federal anti-discrimination law.