I currently have a 256MB slice with Slicehost (apparently quite similar to Linode) and am more than happy with every element of their service. If set up correctly (e.g. use nginx / lighttpd instead of Apache or as a reverse proxy) then you can really get a lot out of such a small amount of hardware.

I can't say it any better... http://www.xkcd.com/552/