The Default
I rent a few VPS from a provider and I don't like their default install image at all.
The partitions are setup in silly ways, I don't trust some of the things they've done to the image, etc.
Starting off they have a /, /boot/, and swap partition to work with.
Luckily this, plus access to the client's GRUB on startup, gives us everything we need to overwrite the system remotely.
Time to swap it back and forth
Once logged in we deactivate the swap partition so that we can use it as a landing zone.
I format it to ext4, doesn't really matter so long as it's not swap and readable by GRUB,
Then mount it somewhere and cd to it.
We download our fresh mini.iso into the new space. I host mine myself for simplicity.
We're done with this image, time to blow this sucka' away!
I do a hard reboot in the console and go to the GRUB commandline.
We can settle this land
Using the grub commands we can load the mini.iso that we just downloaded, and tell grub where the linux and initrd are.
After that we can boot and it should take us to the mini-install.
A new installation is like slipping into a warm bath.
From here on out it should act like a normal installation. The mini.iso is loaded into memory so you don't have to keep the /dev/sda2 partition hanging around.
Obliterating the old sda partitions including our mini.iso, there's no turning back now...
Select some base packages, openssh is helpful for remote machines :)
And that's about it! By the end if all goes well through installation there should be a fresh copy of linux (ubuntu server in this case) on the machine ready for you to do some work.
Tux image from: https://commons.wikimedia.org