Bulk convert PNG-24 to PNG-8 files with best quality

pngquant is exactly the tool for this. It generates palettes better than ImageMagick.

pngquant --quality=0-90 *.png

This will convert all png files in current directory, and automatically choose number of colors to achieve quality similar to 90%-quality JPEG.

(if it doesn't accept the --quality switch it means you have terribly outdated low-quality version and you should upgrade).

GIMP does good job optimizing reduced palettes. It has --batch mode and can be scripted. Also has multiple bindings, so you can write for example GIMP script in Python.

I came across this great tool in my search - RIOT - Radical Image Optimization Tool

Does everything I require and lets you see side-by-side comparison of before and after sample image before you do the batch process.

Update

With the latest versions of RIOT a bug has been introduced that causes some images to be output in greyscale - http://luci.criosweb.ro/riot/bbpress/topic.php?id=471