to answer Cloud121's question, physically change the PPU chips inside the Genesis. that is the only way to upgrade the color pallete.
you can use more colors, by chaning pallettes on the fly, that is, when the screen is drawing, and it reachest the end of a line, and is making it's trek to the other side of the screen, change the pallettes then. one or 2 bytes, nothing for the genesis.