Honestly, a VPS/Dedicated server is overkill for JobRoller. Unless you are getting 100,000 unique visitors/month, you are completely fine with shared hosting or semi-dedicated hosting.
I use MDDHosting
for my jobsite: jobsbayarea.net. It's the fastest webhosting I've ever used - faster than any VPS. They also provide great tech support.
Use coupon code half-price to get 50% off your first invoice.