There's also Virtual Private Servers. These are a touchy subject but in many situations are a logical progression from a virtual server. They fill in the niche between a virtual and dedicated server quite nicely. Various hypervisors used for VPS differ so you really need to educate yourself before jumping on. For example, if configured correctly OpenVZ used by many VPS providers can give you ~80% of the CPU for a short time, when needed. Essentially you get all the functionality of a dedicated server for a fraction of the cost.
I have an account with
VPS Link and the uptime has been 100% for the last 6 months.