O autoremove direito apenas remove pacotes que foram instalados automaticamente como parte de outras instalações de pacotes. As coisas instaladas na imagem são semeadas e, portanto, todas são basicamente consideradas "manuais".
Você provavelmente se livrará do mais deles se livrando do Xorg:
sudo apt-get remove xserver-xorg-core
E depois faça outro autoremove.
Provavelmente haverá outras coisas que você não precisa .. mas ... realmente ... porque não basta perguntar ao seu provedor de VPS por uma imagem de servidor ... não é um pouco bobo que eles até mesmo oferecer a imagem da área de trabalho?