Images - I have seen many cases where the person uploading images (products, CMS pages, etc) is not trained in how to optimize image sizes. There are plenty of articles available online, but a lot of it is just common sense.
- Don't use images for text.
- Use JPEG/GIF/PNG appropriately (ie. generally don't use PNG for photographic images)
- Use sprites for small images since you can pack a bunch of small images into one file giving you only a single HTTP request instead of dozens or more. You might consider font icons as well.
- Save images at the lowest possible quality while remaining acceptably viewable. I find the sweet spot to often be around 50-60 quality for JPEG. Sometimes a quality of 20 is perfectly acceptable, and you might reduce an image from 300Kb to 30Kb. That's big savings.
- Consider lazy loading on image heavy pages.
HTTP Requests - Another big offender. Sometimes there's just not a lot you can do to reduce requests, but you should always try to get this as low as possible. Magento provides some features to help with this out of the box (merging CSS/JS).
Additional DNS lookups - I'd say this is most important for the cart/checkout process. Many stores will have various API integrations that call services. While you can't do much to make an API response from a shipping provider much faster, you can at least identify slow services that aren't going to be readily apparent otherwise. Think about the additional time a checkout might take if you are making calls to UPS, FedEx, USPS, Tax rate providers, Payment providers, affiliate sites, etc.
I think there is often too much importance placed on hosting alone. In the past, I have been tasked with performing certain server tweaks for sites to improve speed, only to find out the home page is loading 20Mb of assets.
Likewise, the Magento white paper on server performance isn't going to be of any use if your site is built sloppy with too much bloat. If your goal is to improve your site's speed, step one should be looking at the pages themselves to find inefficiencies. Only after you've determined your site to be as lean and mean as you want it should you start considering upgrading your hosting.
For the record, a site I manage has been using a SIP-200 on Nexcess for about five years or so and receives an average of 5000 visits a day (it's seasonal, so it peaks over 10k in the late Spring/early Fall). I have absolutely no complaints about this grade of server for this site, and we are running a fairly stock version of Magento CE with thousands of products across dozens of categories.