How do I create a new bitmap with a new size based on an existing bitmap?

You can simply specify the new size in the Bitmap constructor as follows:

[C#]
Bitmap bmp = new Bitmap('exisiting.bmp');
// Create a new bitmap half the size:
Bitmap bmp2 = new Bitmap(bmp, bmp.Width*0.5, bmp.Height*0.5);
this.BackgroundImage = bmp2;

[VB.Net]
Dim bmp As New Bitmap( 'exisiting.bmp')
’ Create a new bitmap half the size:
Dim bmp2 As New Bitmap( bmp, bmp.Width * 0.5, bmp.Height * 0.5)
Me.BackgroundImage = bmp2

If you have to specify a particular Interpolation mode while resizing use the following code:

[C#]
Bitmap bmp = new Bitmap('exisiting.bmp');
// Create a new bitmap half the size:
Bitmap bmp2 = new Bitmap( bmp.Width*0.5, bmp.Height*0.5, Imaging.PixelFormat.Format24bppRgb);
Graphics g = Graphics.FromImage(bmp2);

// Set interpolation mode
g.InterpolationMode = Drawing.Drawing2D.InterpolationMode.HighQualityBicubic;

// Draw image using specified interpolation mode.
g.DrawImage(bmp, 0, 0, bmp2.Width, bmp2.Height);
this.BackgroundImage = bmp2

[VB.Net]
Dim bmp As New Bitmap( 'existing.bmp')
Dim bmp2 As New Bitmap( bmp.Width * 0.5, bmp.Height * 0.5, Imaging.PixelFormat.Format24bppRgb)
Dim g As Graphics = Graphics.FromImage(bmp2)

’ Set interpolation mode
g.InterpolationMode = Drawing.Drawing2D.InterpolationMode.HighQualityBicubic

’ Draw image using specified interpolation mode.
g.DrawImage(bmp, 0, 0, bmp2.Width, bmp2.Height)
Me.BackgroundImage = bmp2