When it comes to Magento performance, having a solid hoster that knows it stuff is highly recommended. The following guide is a listing of hosting providers that should be able to give you a good service when it comes to Magento.
Yireo is not a hosting provider. We don't actively implement Magento shops either - we focus on extensions and training instead. The following list is subjective (our own vision on things), inspired by some customers and friends, and incomplete. Use it as a quick start for a proper investigation.
Besides the official system requirements of Magento, there are couple of recommendations we can make regarding Magento. Here's what makes a good hosting environment for us:
rootaccess, so you can modify whatever you want to modify. If
rootaccess is not available, don't panic: You can ask the hoster to change settings if tuning needs to be done. If they are unwilling to help you tune the server, switch hoster.
root, this will allow you to manage all things yourself. However, if Linux is not your thing, this also means that you need to hire a developer or Linux administrator for setting up things. With managed servers, this administration is done by the hoster. Our experience is that a server needs a lot of management in the beginning, but then requires only a couple of hours of maintenance per couple of months.
rootaccess. This will allow you to add tools like
n98-magerunand other command-line tools to your server. Don't worry if you are incapable of using the shell - your developers will require this (if they are good).
Some well known hosting providers have various VPS packages to help you with. With the specifications above you can find a suitable package easily. Some of these hosting providers are listed below:
A list of Magento hosters on the Magento Wiki can be found here.