KVM com rede virtual e dispositivos de bloco gerenciados via libvirt. Atende a todas as suas necessidades, possui características de desempenho semelhantes às do Xen e permite o gerenciamento gráfico por meio de virt-manager (que você também pode usar para gerenciar hosts Xen, se desejar).
Como sistema operacional host, eu sugeriria o Ubuntu Lucid, o Debian Squeeze ou o Debian Lenny com pacotes de backport (nesta ordem). O desenvolvimento do KVM / libvirt progride a um ritmo constante, então você normalmente quer versões mais novas do que as disponíveis no Vanilla Lenny.
A adoção do KVM é strong o suficiente para que você encontre facilmente sugestões e ajuda para a maioria das perguntas que encontrar.