Now about the server connection:
http://cachefly.cachefly.net/100mb.test - 104,857,600 16.6M/s in 6.5s - Earlier got around 20M/s
ftp://ftp.nfsi.pt/pub/speedtest/100mb.bin - 104,857,600 694K/s in 2m 17s - Note that this is a portuguese server and the only one I know of a file with 100mb
These are downstream into the VPS, outside I can't test properly, because I don't have a good connection for that.
About the server setup etc, being a Gentoo user, decided to install it (I previously checked if it was possible), they provide a recovery image that you can use to boot, and did the installation from there, no problems so far.
Their web interface is pretty simple and easy to use, no regrets so far but I still have 30days ahead.
They experienced a break-in a few months back. Communication to customers was clear, timely and reassuring. (All companies experience problems at some point, it's how they react to those problems that is important. Hetzner's response was very good).
Some small amount of their site/documentation is in German. That's not a big deal (google translate or whatever) and generally it is only the more obscure corners.
Disk size might be limiting on the cheaper offerings (20GB / 7.90 EUR).
I have not experienced the "heavy firewalling" mentioned elsewhere in this thread but I haven't tried putting any serious traffic through it.
Overall very positive.
Recently we leased a Kimsufi/OVH dedicated box with ProxMox installed. Similar price (without setup fee) and it's been running without an hiccup. Had to make a phone call to support about a billing issue (my mistake) and it was immediately resolved.
From my experience, it doesn't get much better quality/price wise than these two, in Europe.
My cousin has been using them for approx. 5 years and he's also very happy with them. He's also had them do a non-standard custom setup for a client before and that seems to have went well and painlessly.