Play a different civ. Civs have specific color sets. There are alternate colors to be used when two civs which share a color are in the same game.
If you play Japan, for example, including the Aztecs in games will get you a different color. If you play Greece, putting Persia in a game will give you a different color.
To make this more common, disable Culturally Linked Starting Locations in your preferences.