As Paolo Gibellini and jsbueno said, the Gimp image mode conversion can calculate an optimized colour palette for as many colours as you want, or can use a colour palette that you specify. The docs are here:
http://docs.gimp.org/en/gimp-image-convert-indexed.html
However, the result will be as you suspected, very pixelated around areas where one colour is transitioning to another. You need a way to separate out lines and fine detail from the predominant colour regions.
The "wavelet decompose" filter is a great plug-in for doing just that. It separates the image out into multiple layers, such that the bottom layer is a blurred version of the image and each successive layer adds extra details back in using "grain merge" mode. Wavelet decompose is usually used for touch-ups and noise reduction, but I was able to put it to use for your purpose.
Here's the process I used:
Apply wavelet decompose with the default settings, then (in the Layers toolbox) successively turn off the visibility of the top-most layers until you find a level of blur that show solid colour blocks but still has the important detail. That was wavelet scale 4 for me. The layers above this will be your "detail" layers and the layers below will be your "colour" layers.
Make all your layers visible again, and use "merge down" to combine all your detail wavelet layers together (i.e., wavelet scale 1, 2, and 3 for me) and and all your colour layers together (i.e., wavelet scale 4 and 5 and the wavelet residual). Be careful not to merge your original image, in case you decide to start over. You'll have to manually set the mode on the merged detail layer back to "grain merge" -- it switches to "normal" when you merge.
Select the merged colour layer and copy it, then paste as a new image (you need to do this as a new image, since indexed mode applies to the whole image, not just one layer). On the new image, go to Image>Mode>Indexed and pick the colour settings you want. (If you don't like the results, undo and try again with different colour settings.) When you've got a good colour-palette, copy the image, go back to the other file, and select "paste as new layer". In your layers toolbox, move the pasted layer to be underneath the details layer (which should be in "grain merge" mode).
Select the details layer, and go to Color>Desaturate. Pick a desaturate mode that looks good to you (I used luminosity). By desaturating the details, you make sure that they only add gray lines, not new colours. The details layer on top of the converted colour layer should give you the colouring book effect you're going for. If you want to actually create a colouring book, you need another step:
Duplicate the converted colour layer. Go to Filter>Edge-detect>Edge and find a set of options that finds the edges nicely (I couldn't tell much difference between them, and just went with the default). The result will be a layer with coloured edges on a black background. Use Color>Invert to get a white background, and then use Color>Desaturate to make it grayscale. To make all the gray lines equally dark, go to Color>Levels, and move the middle selector in "Input Levels" (i.e., the gamma correction value) to the right. The edge layer, plus optionally the details layer on top, will now be your colouring book outlines.
If you want to combine the edge layer with the colour layer, use Color>Color To Alpha to make the white areas of your edge layer transparent.
Original:
Simple conversion to a 16-colour palette:
Colour-block version of the 16-colour palette:
Colouring-book style edges for 16-colour image, plus grayscale details:
Colour-block version with edges and grayscale details on top:
Colour-block version with edges, no details:
I don't know what age range you're going for -- that final image is rather complex. Steps to try to create a simpler image:
- use a more blurry version of the image for the colour indexing step,
- use fewer colours
- use a high-contrast colour palette instead of letting the computer pick an optimized palette (the computer optimization is intended to preserve as much detail as possible).
