quando você quiser ir com as últimas versões, você deve usar o fedora. centos / rhel é feito por muito tempo, uso estável. não haverá as atualizações mais recentes incluídas, apenas atualizações para correção de bugs.
Eu aluguei um VPS e ele será usado como um servidor LAMP.
Eu gosto de usar versões mais recentes dos pacotes LAMP e aplicar atualizações a eles usando o yum em vez de 'compilar a partir da fonte'.
Como você já deve saber, por exemplo, instalar a versão mais recente do PHP requer a adição de um repositório extra como o remi no CentOS, enquanto o repositório oficial do Fedora já inclui as versões mais recentes dos pacotes LAMP.
O VPS tem apenas 256MB de RAM. Qual sistema operacional deve ser escolhido?
A diferença entre o CentOS e o Fedora é "Estável" v.s. "Bleeding edge". Então, se você quiser que um servidor experimente: Vá para o Fedora e esteja preparado para reinstalar a cada ano.
Se você quer um servidor 'estável' com ferramentas adicionais: Vá para o CentOS e adicione o remi mencionado e talvez até mesmo o EPEL repository (que é basicamente útil para o Fedora back-ported para o RHEL / CentOS).
O Fedora não tem mais a edição "Server", e você encontrará que a edição padrão é muito grande e contém vários programas destinados ao usuário de desktop. A última versão que eu instalei também tinha o SELinux habilitado, o que produziu um comportamento errante e levou algum tempo para descobrir!
Se você está feliz com a administração do RHEL, eu instalaria o CentOS e atualizaria usando os repositórios do remi, já que você terá muito menos configuração inicial para fazer. É claro que se seus hosts VPS o instalarem para você, então não há muita comparação, e a facilidade de atualização do Fedora provavelmente venceria.
edit: Com relação às versões mais recentes do software, como a questão observa, os repos do remi o manterão atualizado.