UnixGuru Hosting

I see that you can purchase Ubuntu Desktop VPSs from other hosts that you can RDP to from windows, do you provide those?

Simple answer is "Yes"

Purchase a VPS with enough memory for a desktop (2GB or more) and PuTTY in and run the following commands as root.

apt-get purge apache2* bind9* samba*
apt-get install ubuntu-desktop
apt-get install xrdp
apt-get install xfce4
echo xfce4-session > ~/.xsession
service xrdp restart

Now RDP in using your Windows Remote Desktop Client