Oh now an additional comment before everyone chimes in. I realize that the image isn't going to be 1:1 to the original. Realize that the kindle does not dither ~ the same as you may expect. If you like dithering, configure it. I think kindle dithering looks bad, so I don't use it. Different types of dithering may give you better image quality depending on the media/content you are viewing. You can tweak smart blur as I said and dithering to get better quality/artifact removal. However. The kindle uses a hybrid dithering system, where it does not dither, but it uses a high threshold for colors/contours to exaggerate detail. Using the image manipulation techniques here I believe you can get a very similar result to putting in a source image (unscaled, full color) and taking a screen shot with the kindle (alt+shift+g) to produce a gif. Compare that GIF to this converted image and you will see that they are very much the same.
I still need to tweak it a bit to get more detail in general, but I think the palette is correct. Any feedback will be helpful.
The kindle still does a Slightly better job at converting a color image to 16 shades of gray, but I think that's just because I don't have the filters set up correctly.
*Edit - with the PS plugin you will get about the same dithering pattern as the kindle, better quality if you tweak it.
Denoise+Sharpen filters will give you some interesting results on line art. You can significantly sharpen/increase readability and contrast on simple art with this. Also tweaking LEVELS can help achieve better contrast with some black/white works (manga).
Edit: OK found a free plugin that does exactly what I need will update guide after I get it working and example:
http://www.ximagic.com/g_download.html
Here is what Dispersed Dot Bayer 8X8 looks like after these transformations int he picture viewer on my DX