[shuzchen]

Any reliable VPS offering should support custom kernels -linode, prmgr, and ec2 do. While it's not "any OS you want", they support any kernel that runs under Xen, which pretty much opens the door to most distros you'd want to run a server with. Really, the only thing you're technically locked out of is Windows.

[Illniyar]

ec2 has windows.

[joshstrange]

Right but you have to pay extra for Windows instances. I think shuzchen is saying you can't install windows yourself at the linux box prices (EC2) whereas with a dedicated box can run whatever you want.