One thing that has been the topic of discussion lately is what type of server works best for Magento. The to this is that there is no one solution but there are a few things that can help. Especially when it comes to multi store setups.
The first thing is the server itself. You are going to want to get a VPS (virtual private server). Shared hosting can be ok but you really do not get the control you need to take advantage of your setup. From my experience you will want between 2-3 GB’s or ram per site you are hosting. Another option and one that I am finding out works better more and more is to have mysql run on its own server. The advantage of this is that mysql has its own ram and its own cpu so you can allow mysql to basically use all the resources on the server. The way i would split the ram is a 1:2 ratio. For every 1 GB of ram on the server your mysql server should have 2 GBs.
There are a couple of things you can install to help your sites especially if you are running the community edition. The first thing would be to run your site using Nginx instead of apache. I usually do this for my enterprise clients. The downside is that it can be a pain in the ass to setup. No installation on Nginx has ever been quite the same for me. As for my community edition clients I have them use apache and since community does not support full page caching like enterprise, I install Varnish Cache. This helps a lot in terms of making your sites faster. It makes the site feel like you are hosting static pages because thats basically what varnish does.
Lastly there are things you should do no matter what version of Magento you are using and that would be install Memcached and APC cache. Both will help your sites tremendously but for community edition users the big one is Varnish Cache with Memcached and APC.
On a side note for operating system, I have set these sites up on pretty every type of linux. Red Hat Enterprise, CentOS, Debian and lastly Ubuntu. In my experience none of them had an advantage over the other. They all worked basically the same so pick the one you are most familiar with. I tend to do either Debian or Red Hat Enterprise for my own servers.
As always let me know what you think and what setup are you running for your Magento stores?