The color comes from the soldermask, so what you're really asking is what colors of soldermask are available. The answer is that you can get just about any color soldermask, but the less common ones may cost more depending on your manufacturer. Different manufacturers offer different standards. One manufacturer may only offer green as standard and you'll need to pay a premium for blue, red, etc.
To answer your main question about what is commonly available, I have seen green, blue, purple, red, black, and white. Those seem to be the most popular. At work we use green boards to indicate leaded assemblies (because in the past, prior to RoHS restrictions, all of our boards were done in green), blue to indicate RoHS-compliance, and red for prototypes. There is no "best color", it is completely up to you. Personally I don't care for black soldermask or white soldermask because it is difficult to see the traces which could be useful for troubleshooting.