But then there's the problem of different Pokémon having different numbers of colours in their palettes (even different numbers of shades for each colour), so that wouldn't always work. If they did that, you'd end up with some really bad-looking eggs...
I'm assuming that the game does a sort of colour-by-number method of handling sprites - that is, it replaces colour A with colour B when making a pokemon Shiny.
What this means is that it's a defined set of, say, GIF colours, and the shiny just uses a different set of GIF colours (GIFs store image information by numbering each pixel, and then having a colour alotted to each number - much as how, i QBasic, if you tell it to colour the screen "2", it makes the screen, if I recall correctly, red - and 10 is dark red, and 9 is grey). I'm assuming that this is how pokemon games change the colours of pokemon for Shinyness (it's how I understand the phrase "palette swap", at least - indeed, in QBasic, there's even a command to perform a palette swap).
All that would happen is that the egg would be given colours matching the normal palette of the pokemon inside. If there's any issue with what the egg looks like, it would be just as easy to have predefined palettes for each family of pokemon, to ensure colour-consistency. So, for instance, perhaps the eggs are done so that you get two differently-coloured spots on a surface of a third colour - each of which would have two or three tones. Perhaps the Pikachu line would have eggs with a pikachu-yellow base colour, half the spots black, and the other half Raichu-orange. But if it were the Wailmer line, perhaps it's a cream colour egg (Wailmer's bottom half), with half the spots dark blue (Wailmer's top half) and the other half lighter blue (Wailord's top half).
It's simple, requiring at most a palette swap between eggs, thus requiring only a single egg sprite, and maybe 200 sets (I assume that's the approximate number of unique pokemon families) of maybe nine defined colours (which means RGB data of nine colours).
EDIT: To demonstrate what I mean, I've grabbed a picture of a pokemon egg off Bulbapedia, and edited its palette to fit the Pikachu line. Here's the original and the Pikachu version:
Obviously, not a perfect example, since I just did a really quick mockup using an existing egg sprite - the egg sprite would be designed specifically to suit this method.
.
