Try one of these:
Bitmap newImg = new Bitmap(newWidth, newHeight, System.Drawing.Imaging.PixelFormat.Format16bppRgb555);
Graphics newGraphic = Graphics.FromImage(newImg);
newGraphic.DrawImage(myImage, 0, 0, newWidth, newHeight);
newGraphic.Dispose();
newImg.Save(myPath);
or
Bitmap newImg = new Bitmap(newWidth, newHeight, System.Drawing.Imaging.PixelFormat.Format16bppArgb1555);
Graphics newGraphic = Graphics.FromImage(newImg);
newGraphic.DrawImage(myImage, 0, 0, newWidth, newHeight);
newGraphic.Dispose();
newImg.Save(myPath);
or
Bitmap newImg = new Bitmap(newWidth, newHeight, System.Drawing.Imaging.PixelFormat.Format8bppIndexed);
Graphics newGraphic = Graphics.FromImage(newImg);
newGraphic.DrawImage(myImage, 0, 0, newWidth, newHeight);
newGraphic.Dispose();
newImg.Save(myPath);
This should only slightly degrade the quality and drastically reduce the size, Im not sure which one would be better though.
Here are a whole bunch of other options to try as well:
http://msdn.microsoft.com/en-us/library/system.drawing.imaging.pixelformat%28v=vs.110%29.aspx