Yes, I would rule-out shared hosting.
Do not rule-out VPSs. But do make sure that you get a guaranteed CPU% (this will be the case with Xen VPSs, perhaps others), and make sure you know how many VPSs are hosted per physical machine, and what hardware is being used.
Virtual servers don't have the speed of dedicated servers, but perhaps you don't need a dedicated server. Also, make sure you compare apples with apples - A 1/10 share of a dual or quad high-end server could be as fast as 1/2 the speed of a low-end dedicated server (or more).
One advantage of virtual servers is that (given good management practices) you can be quickly moved from one machine to another in case of failure, need for added capacity, etc. Of course this should be true in theory with dedicated servers, as well. (The key being "good management practices".) Of course, if you own your own servers, you need to make your own redundancy and disaster-recovery plans.
Make sure you do the "phone test". Pick up the phone, and call the host, with a technical question. See how quickly you get to a real technician, and how well they are able to answer your question.
Consider the colocation facility (security, backup, etc.), it's physical and topographic location (is it in the network-topographic and physical center of your users?), the carriers (are they tier-1?) and the available carriers (can they expand?)
You want a host that connects to multiple tier-1 carriers in a major data center, not one at the end of a long one-lane road. traceroute to one of the host's customers (NOT the host's own website!) from multiple locations (you can find many websites around the world that will let you do this), and satisfy yourself that they have connectivity through multiple tier-1 carriers. Look for direct peering with major non-carrier networks as well - Cox, Time-Warner, AOL, Yahoo, Microsoft, etc. A good host will be in a datacenter that will peer directly with one or more of the above, who may even have servers on-site. (Do you need to access Google services, for example?)
It may not be easy to find hosts that meet your criteria, but it is easy to rule-out ones that don't. :)