RDP es Remote Desktop Protocol, osea Protocolo de Escritorio Remoto. Es una forma de conectarte a un servidor. También existe VNC que es muy popular.
VPS es Virtual Private Server, que significa Servidor Privado Virtual. Que no es más que una máquina virtual.
Las empresas que ofrecen "RDP" en realidad lo que hacen es ofrecerte una cuenta de usuario sea en Windows o en Linux, en una maquina virtual (VPS), o en un servidor dedicado y te otorgan distintos privilegios según el plan que elijas. Por lo tanto en un VPS tu manejas la máquina y puedes hacer lo que quieras con ella, es como tu PC.