It seems to me that the workloads on Digital Ocean are not fully utilizing the block device. FIO shows about 50% util for DO, and 81% for Linode on the queue depth=1 test, and 70%/82%, respectively, on the queue depth=8 test. Which seems to indicate a bottle neck somewhere else (at least on DO), and that seems to align with OP's statement at the end, where it seems DO is being capped. Also as it was pointed out, the sizes of these VPS are not even mentioned, and most likely the working set size of 128MB, might be either too small or too big for any of these VPS, making even harder to see the value of these results.

Brendan Gregg has excellent info on these topics,

http://www.joyent.com/blog/benchmarking-the-cloud http://dtrace.org/blogs/brendan/2011/05/11/file-system-laten... http://dtrace.org/blogs/brendan/2012/10/23/active-benchmarki...