[anelson]

FWIW, I've tried the Scaleway (Paris), MacStadium (Atlanta), and as of today also the Hetzner (Falkenstein, Germany) M1 offerings.

The Scaleway service had such awful latency on the VNC connection that I found it almost completely unusable. MacStadium and Hetzner are both better. That's particularly odd because I'm based in Kyiv, Ukraine, so I would have expected better latency to Paris than to Atlanta. It might have been a problem on my ISP's end, I didn't spend any time looking into it.

Besides that, the Hetzner offer is by far the cheapest, as is usually the case with Hetzner. If you don't mind having to do all configuration yourself, and you don't require a flashy whiz-bang UI for managing your provisioned resources, Hetzner is a great value.