Latency: How long does it take for data to get from point A to point B? Latency of 50ms to 100ms or less is what you should look for. Note that you won't be able to control latency but anything over 100ms is likely to exhibit lag in the RDP session.
Capacity: How much bandwidth do you need? If you run multiple applications in the remote session, run the session in full screen and/or spanned monitors, if you configure the RDP client to use 24 bit or 32 bit color, if you enable resource redirection (local printers, drives, etc) then you should plan on having bandwidth of 100Kbps for the RDP session itself. This doesn't account for any other bandwidth needs that you have that are unrelated to the RDP session.
100Kbps is the number I've come up with in my RDP performance tests. A lot of people are going to disagree with me, but a heavily used RDP session (resource redirection, full screen or spanned, many applications running concurrently requiring lots of screen redraws) averaged about 100Kbps over an 8 hour period in my tests. That being said, I'd rather have more capacity than I need then less.
It's less about the speed of the connection and more about the latency of the connection. I use a similar arrangement for consulting and monitoring from a central data center-based environment. Anything under 50ms is more than acceptable. Ideally, you'll have a connection speed greater than 1.5-megabits/second. If using raw RDP, setting a lower color depth and resolution will help. On your hosted system, disable themes and use a basic desktop background.
One thing that's helped me when I'm farther away or have higher-latency links is using an RDP accelerator. I use a single instance of Ericom Blaze, which employs compression and other techniques, for this.