Digital Ocean has become quite a competitor (and I have a box with them now for a staging environment) but the fact that they do not provide a private/internal network between your boxes is something that I can't live without. I like to keep app servers and db servers isolated from the real world by one box in front of all of them ... which is not something you can currently do with Digital Ocean.
I love Heroku's platform and think they've done some amazing things for our industry, but I don't agree with any of their recent PR moves. Linode, on the other hand, has never stirred up drama or bullshit since I have started working with them. They're straight shooters and this gives me a great deal of confidence.
I had a personally hair raising experience this weekend trying to migrate a smaller server that kept swapping over to a larger one without too much downtime. I was able to do this pretty painlessly but man I wish I would have waited just a few days for this!
Digital Oceans lack of "private" network is silly, if you really need it, setup a encrypted tunnel yourself, I would not trust anything else anyway. Also I highly doubt that if your DO DB and App server talk the traffic leaves the datacenter, but you could test this.
How long ago was this?
By all means, encrypt your traffic on the private network if you're so inclined, but encrypting across the public IP space and encrypting across RFC 1918 space do not accomplish the same goal, particularly not with the same latency or redundancy characteristics.
Nothing about the use of a public addresses forces an extra hop in the way you suggest.
Here is a counter example, imagine I have two VM host servers with 16 logical cores. On one I could pin each VM to 1 logical core, on the other I could run 300 VMs and give each VM 24 logical cores... The first one is going to perform much better.
Also some hypervisors (for example VMware) only executes a VM when they have as many cores as the VM has cores available for execution. So having many logical cores in your VM can negatively influence CPU scheduling.
"And support is a joke."
Not in my experience
Based on the benchmarks I've seen, it appears that Linode really does give the kind of concurrency you'd expect from four cores (i.e. if your problem is parallelizable, you can scale up on Linode better than Digital Ocean, whereas Digital Ocean will work much better if your program is serial and needs to hit the disk a lot).
Your hand-waving about the hypervisor is unwarranted, since hypervisor interference under Xen shows up as its own time from the perspective of the domU (steal%) and nobody worth mentioning actually does hosting with VMware.
You don't know if the first one will perform better or not. It depends on the workload of each VM. If most of the VMs are idle most of the time, when one of them needs CPU the second setup may even perform better.
And I doubt that Linode runs more VMs per host than DO. Judging by the pricing is probably the other way around.
Good thing Linode and DigitalOcean don't use VMware.
On the other hand as far as I know DO don't tell how many VMs share a host.