Really depends, you can get a whole range of servers with different specs. If you're planning on running a small retro then maybe look into a game server simply because its built for gaming and no tcp proxy would be required. If that price range is out of your area then you can look at the cheaper option such as windows server that starts at £4.99.
I recommend xhosts for obvious reasons, however if you're not interested in a reseller then you can look at...
if you're using a computer there should be a program on your computer called Remote Desktop Connection and when you buy a vps the host that u bought it from should email you the details to login to your vps.
the last vps i bought was from cheapwindowsvps.com and it was fairly cheap with decent customer service, i believe 20$ for 2gb ram which i think is decent for a starting hotel but u can get a vps from any site u wish
@GlennRetros , that VPS is garbage, I could get like 8gb for $20, so the name of that site is obviously misleading and makes people think that they are "cheap", I'd suggest not using that host as there are others out there with better deals and great service.