Divulgação: Eu trabalho para o Linode.
360 MB é uma boa quantidade de memória, mas não é nada para telefonar para casa quando se trata de pilhas LAMP. Você precisa estar totalmente ciente das maneiras de otimizar sua pilha nessa quantidade de espaço; um sistema operacional de 64 bits impedirá diretamente esses esforços usando mais sobrecarga de memória para algumas coisas. Conhecendo cada uma das distribuições que você listou como a palma da minha mão (eu construí algumas delas), você é realmente melhor com o Ubuntu.
Eu rodei o Debian no jedsmith.org e no Ubuntu no meu Linodes de desenvolvimento, e eles são provavelmente os mais eficientes do lote; O Ubuntu, sendo o atual precursor das distribuições, fornecerá tudo o que você deseja - segurança, desempenho e uma grande comunidade para responder a perguntas.
Grandes opiniões de cletus:
I'm half-tempted to suggest Arch Linux just for a barebones distro where you only install what you need as unnecessary packages can eat up your memory really quickly.
Eu também ouvi o mesmo sobre Arch, mas ainda não tentei. Outro empregado da Linode, Sam, jura pelo Arch e tem muitas coisas boas a dizer sobre isso.
Also, re: LAMP stack, consider using nginx instead of Apache for better performance on a low end VPS slice.
jedsmith.org é o nginx na frente do FastCGI PHP, e ele grita como o inferno.