Obviously the only problem is the original image dimensions. The image itself is too small and Acroread’s image scaling routines cannot produce anything acceptable from it.
Unfortunately from PDF we cannot choose applied image scaling algorithm. The only available PDF option is to force to interpolate the image, which usually gives even worse result (when applied to tiny images).
As a workaround I would recommend to generate images with greater dimensions (keeping height/width attributes unchanged) as it described there: