> If it's wrong(and illegal) to pay people differently based on their race or gender, I can't see how it should be alright to pay people differently based on their cost of living.

It makes no sense to equate location with immutable characteristics like race or gender. People can move to a new city.

> There ought to be a movement to outlaw this practice.

State and municipal minimum wage laws would be neutered by such a law.