I think this is the essential point, the smaller ones often have no data points either way regarding security. That said, there are some great cheap ones http://www.lowendbox.com/
redirects me to
https://twitter.com/#!/LebAlerts
From their twitter stuff, LEB has been getting DDOS'd for the last day?
They also make a few references to Linode - how are are/were they using their service?