Paint.NET for Mac for pixel by pixel art creationg
Though it is more of a Photoshop clone by its number of features, have you considered The Gimp? I don't know if it is going to fit your exact requirement, but it does have an excessive number of features including a magnified editing mode and color substitution.

Otherwise, have you tried Paint.NET via Wine? It seems that only the v3.5.x version might get somewhere, but with limitations.