Document your needs, and check out the specs.
I won't list them here, but there are probly ~6 hosts that are most common in the US and UK, and they have mostly satisfied customers, and experience with solid uptimes and performance.
Do you need windows to support ASPx or the like?
If not 'Nix hosting will be substantially cheaper.
What language do you use?
Java applications tend to have a larger memory footprint then something like PHP, so plan your required memory accordingly
How many sites do you run?
Why? ..
Database Limits
Some hosts will set arbirtraty limits on the number of databases, encouraging poor habits like multiple applications sharing the same instance, with different prefixes.
Bandwidth Limits
Now a'days most decent hosts have unlimited bandwidth and storage -- those are just too cheap to be worth enforcing limits.
Security
DO you sites need SSL? Then you will likely need a static IP as well, which can be a major pricing point difference among providers.
Access
Do you just use rsync/scp, or do you need shell access? DO you install applications and need root access? Do you want to be able to muck with Apache/nginx config, or leave that to a web panel -- or do you want both options?
( I see this as the biggest motivation to move to a VPS, the ability to manage, re-configure, and reboot your server without waiting on support tickets.)
