Possible to reproduce the "resize image" quality of Paint.NET?

Question

I have been having a tough time creating a thumbnail that is not horrible quality. So far the best code i've come up with is:

Bitmap bmp = new Bitmap(width, height);
Graphics graphic = Graphics.FromImage(bmp);
graphic.InterpolationMode = InterpolationMode.HighQualityBicubic;
graphic.SmoothingMode = SmoothingMode.HighQuality;
graphic.PixelOffsetMode = PixelOffsetMode.HighQuality;
graphic.CompositingQuality = CompositingQuality.HighQuality;
graphic.DrawImage(photo, 0, 0, width, height);
return imageToByteArray(bmp);

Which produces this gem:

If I resize the same image in Paint.NET i get this:

Which is WAY better. Everything I've found on line points me to some variation of the code I have above. I know Paint.NET was open source at one point. Does anyone know what magic they were doing to create such nice resize functionality and if that functionality can be reproduced in C#?

UPDATE:

The original image from this example was a jpg

Answer 1

GIFs

I recalled reading that .NET has issues with palette-based formats, like GIF, so I dug up a few articles.

This article describes how to quantize (pick an optimum palette) to improve quality: http://msdn.microsoft.com/en-us/library/aa479306.aspx, as does this (badly formatted) article.

In brief, I believe GDI+ picks a non-optimum palette when performing the resize.

PNGs

PNGs are palette-based, so they may be prone to the same issues as GIFs. I'm not sure if it matters that the palette can be much larger.

JPEG-friendly example

This code should work fine on JPEGs (but does not render GIFs smoothly). If you try it and it pixelates a JPEG, then there is probably something else going on.

private static byte[] GetScaledImage( byte[] inputBytes, int width, int height ) {
    Image img = null;

    using( MemoryStream ms = new MemoryStream() ) {
        ms.Write( inputBytes, 0, inputBytes.Length );
        img = Image.FromStream( ms );
    }

    using( MemoryStream ms = new MemoryStream() ) {
        using( Image newImg = new Bitmap( width, height ) ) {
            using( Graphics g = Graphics.FromImage( newImg ) ) {
                g.InterpolationMode = InterpolationMode.HighQualityBicubic;
                g.DrawImage( img, 0, 0, width, height );

                newImg.Save( ms, img.RawFormat );
                return ms.GetBuffer();
            }
        }
    }
}