I recommend OVH.com. They provide bare metal servers in a semi-automated way and have locations in US, Canada and France.

For the type of application that I run, where our demand is not very elastic, I find it very cost-effective and more flexible (as long as you're comfortable with administrating KVM and ZFS). I also like that with ZFS, I can easily sync snapshots between providers at the filesystem-level.