A VPS is a VPS ... but the devil is in the details. VPS customer chooses the OS ... Ubuntu vr x an y, Debian x or y, CentOS x or y. Howard is right ... you'd want a long term support version of whatever you choose. And customer also chooses if the VPS is managed or un-managed - the latter means you save but you also do.
Those devilish details are two fold and both software and hardware with the goal of future proofing your site as much as one can at present ... knowing full well that advancements in this sort of technology might very well pass your 'caddie' in a few years time frame.
Software: the availability of higher versions of PHP, MySQL/MariaDB, Ngnix/Apache as well as the extras one will need if one desires all the features of a 3.1 (unoconv, Global Search - please research those separately rather than asking for a summation here.).
Hardware: OS might be X or Y, but one does have options upon which to place the OS. You've given a link to OHV hosting but asked about Rackspace (assuming UK). Now one is talking drives and hardcore techie stuff.
Both probably offer such tech that's close ... and from what I've been to read/see on the topic ... debated in thse forums from time to time.
A tool for benchmarking ... folks have shared their results:
https://moodle.org/mod/forum/discuss.php?d=335357#p1351573
They've also shared their specs.
BTW, from what I've seen ... version 1.9.19+ runs ok on boxes where 3.1.1's also run.
Amazon and Google have similar offerings.
"Best" dependent upon multiple factors ... upon which many can only provide their stories ... your mileage might differ, in other words.
And, of course, there is also how much does it cost. Can only say two things ... it's true, you get what you pay for ... and can't get blood out of a turnip! ;)
'spirit of sharing', Ken