Do this on your local/home computer, not the server.
Open up Remote Desktop:
Click the Show Options dropdown in the bottom left corner.
Go to the display tab and look for Colors.
You can choose any of the four options, dropping down a few bits should drastically help improve your connection.
You should be good to go after this.