The main advantages over something like a VPS are having a dedicated full-sized hard drive and being able to run any OS you want on bare metal (they support remote iso installs via kvm and vnc). If you choose a non-atom processor you can also run your own virtual machines on these.
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.
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.