Who would you suggest then instead of Linode? I was thinking of renting their smallest one to have something to fart around with.

If you want something cheap to fool around with, there is:

http://nosupportvpshosting.com/

I just set up a VPS there to try out. No idea on reliability yet, but it does seem like a lot of (virtual) server for the money.

Prgrmr.com

Is this a joke? Looks like a malware site.

That does look like a malware site. It was a typo. Here's the correct URL:

http://prgmr.com/

That one looks quite good, I like the Ascii art design and the "the 64M option is an 'advanced option' - we don't have any distros setup that work well in 64 megabytes. You can strip down most distros to the point where they will work well, we just have yet to do so. If you still want to order it, use 'view source' to find the commented out link. "

futurevps.de

Based in Germany, amazing support.

Edit: I'm German, but not affiliated. I do have a small vps hosted there for a while though.

Linode uptime varies according to data centre.

Lots of people use the Fremont centre. It is a dud.

I've hosted in Dallas without incident and currently I use Tokyo.

citation or proof of claims ?