Did you try multiple instances on each provider? Performance between VPS's from the same provider varies wildly. If there are 64 VPS's on a server, you will probably get a lot more than 1/64th of the processing power of that server because most of the other VPS's are idle. But how much more than 1/64th you get will vary wildly from machine to machine.
This absolutely should not be true, and in my experience it isn't true on Amazon -- you will neither be starved for resources if others do intensive things, nor will you enjoy riches if they are quiet: You will get what you are paying for.
I have a personal experience from Digital Ocean that is a bit different. Firstly let me say that I think they have a great service and compelling prices, but I set up a test server (the 2GB/2CPU variant) to trial leveraging it in the platform mix, as a solution that crosses host providers = awesomeness.
The IO performance I got was terrible, despite all of the talk about SSDs. Simple operations would stall, the CPU endlessly waiting on wa. I submitted a support ticket and quickly they toggled some priority flags and I started getting performance more along the the lines of expectations, but ultimately it seems like a classic case where single tenants can completely monopolize the platform, enjoying the entirety of the storage platform at the cost of everyone else. I'd rather that they cap consumption and do appropriate IO quanta allocations rather than leaving VMs starved.
And it really makes me concerned for the future -- do I have to constantly do benchmarks and analysis, hopping VMs just to find one that isn't an abomination? That isn't how these things are supposed to run.