C# - Picture resizing causing unnormal huge qualit

I have an MVC application where user upload an image and I'm resizing it for them if its needed. Larger pictures get a really bad quality when resized but smaller picture which don't need to be resized stay at a good / expected quality

Large picture:

This one is scaled to 50KB

This picture only gets a reduced BPP:

And the reduced version looks like this:

How can I reduce the file size without losing that much quality ? At the moment I just resize the picture.

This is the code:

                Request.InputStream.Position = 0;
                string Data = new System.IO.StreamReader(Request.InputStream).ReadToEnd();
                var Base64 = Data.Split(',')[1];
                var BitmapBytes = Convert.FromBase64String(Base64);

                while (BitmapBytes.Length > 51200)
                {
                    int Schritte = SetSchritte(BitmapBytes.Length);
                    var format = Bmp.PixelFormat;
                    Bmp = ScaleImage(Bmp, Bmp.Width - Schritte, Bmp.Height - Schritte);
                    ImageHelper.ChangePixelFormat(Bmp, format);
                    BitmapBytes = ImageToByte(Bmp);
                }


        public static Bitmap ScaleImage(Image image, int maxWidth, int maxHeight)
        {
            var ratioX = (double)maxWidth / image.Width;
            var ratioY = (double)maxHeight / image.Height;
            var ratio = Math.Min(ratioX, ratioY);

            var newWidth = (int)(image.Width * ratio);
            var newHeight = (int)(image.Height * ratio);

            Bitmap newImage = new Bitmap(newWidth, newHeight);
            using (Graphics gr = Graphics.FromImage(newImage))
            {
                gr.SmoothingMode = SmoothingMode.HighQuality;
                gr.InterpolationMode = InterpolationMode.HighQualityBicubic;
                gr.PixelOffsetMode = PixelOffsetMode.HighQuality;
                gr.DrawImage(image, new Rectangle(0, 0, newWidth, newHeight));
            }
            return newImage;
        }

        private int SetSchritte(int length)
        {
            if (length > 51200000)
            {
                return 400;
            }
            else if (length > 512000)
            {
                return 200;
            }
            else if (length > 102400)
            {
                return 50;
            }
            else if (length > 55000)
            {
                return 30;
            }
            else if (length > 51200 && length < 55000)
            {
                return 10;
            }
            return 500;
        }

As Hans Passant said in his comment: Always start from the original Image if you want to shrink your Bitmap more.

As well you can try this approach which does all the reduction in one line. The only problem with it is that you will always end up with the PixelFormat PixelFormat32bppARGB.

float ratio = 0.1f;
Bitmap reduced = new Bitmap(original,
                            (int)(original.Width * ratio), 
                            (int)(original.Height * ratio));

Edit: To solve the Problem with the Pixel Format add this line.

Bitmap adjustedPixelFormat = reduced.Clone(new Rectangle(0,0,reduced.Width,reduced.Height), original.PixelFormat);

Edit: To estimate the right ratio:

int desiredSize = 51200;
int originalSize = OriginalBitmapBytes.Length;
double ration = Math.Sqrt((double)desiredSize/(double)originalSize);
// Do not change Image, if already small enough...
ratio = ratio >= 1 ? 1 : ratio;