This is a known problem in computer science called dithering: your picture has too many colors for the target format or display to show (for example animated GIFs are limited to 256 colors) so what you can do is simulate the colors in between through juxtaposition.
Dithering might not work very well if your picture is going to be seen from up close; you can also near to the closest color from those 16. Again, this is a solved problem and a computer can do the maths for you.
Here's what you can do to get the best results a computer can give you.
- Get Gimp, install it and open it.
- Get a picture of the wool palette in your texture on screen; just opening it in an image viewer or the browser is fine. Keep it unobscured from all of the open dialogues, including the ones we're about to open.
- Open the palette editor (Windows → Dockable dialogues → Palette)
- On the bottom bar of the palette editor hit the create palette button.
- In the new dialogue that pops up, call the picture Minecraft.
- From the main Toolbox, double click the primary color from the color chooser (it should be the large black rectangle obscuring the white one.) You should get a color picker. Don't close the color picker. If you close it, simply double click that rectangle again.
- Find the eyedropper button next to the HTML notation textbox. Click it.
- Move your mouse over the picture from step 2. Press and hold the left mouse button, then move it around. You will see that the color picker changes the current selection to reflect the color that's under your mouse. Mouse over the first of the 16 colors of wool in your texture pack and finally release the left mouse button. Repeat the process until you get a satisfying representative color for that wool block.
- Go to the Minecraft palette window, right click in the middle and choose New color from FG to add the current color to the palette.
- Repeat steps 8 and 9 for each of the 16 shades of wool. If you want to use more than that (e.g. ender blocks or netherrack or what have you), do the same for those blocks, too.
- Close the color picker.
- Open the picture you want to convert.
- Size the picture down (Image → Scale Image...) so that you get 1 pixel per block (i.e. if your picture in Minecraft will be 40×30 blocks wide, scale the image down to 40×30 pixels).
- Finally we get to the business part. Open Image → Mode → Indexed...
- Choose Use custom palette
- From the palette list (the one in step 3), drag the Minecraft one and drop it on the palette chooser (the button with the tiny colored rectangles.)
- Choose if you want dithering or not. You will probably want either Floyd-Steinberg (reduced color bleed) or No dithering.
- Hit Ok.
Now the picture tells you what block you should use where in your final result. You can zoom with Ctrl-Mousewheel and pan around with middle click. Now you just have to go minecraft the picture together with wool.
For example, here's how this process changes a picture of the color spectrum with Floyd-Steinberg (reduced color bleed) and these wool colors:
If you don't like the dithering, you can turn that off and approximate every pixel with the closest color:
...so yeah, feel free to consider this picture as proof that the Minecraft selection of wool dyes is not the very best ever. Here is the same image with the same algorithm and the same number of colors; all that changes is the 16 specific colors:
Of course, the more complex the starting picture, the more disappointing the result will be. Picking the right picture matters. Cropping it to the part with more details helps too.
Here's another example: kitten.
Okay, that doesn't look too good, but while you are using GIMP you might as well make use of it. The background is midway green and yellow, so maybe you can consider shifting the hue of the image (Colors → Hue-Saturation) towards either one of those two colors. For bonus points you might even try and just do that to the background using the various selections tools (this is no GIMP tutorial!).