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.