Os sites que você está visitando provavelmente falam sobre o uso de RAM; Eu nunca vi um provedor VPS fornecer apenas ~ 350 MB de espaço em disco.
Com isso dito, quase todas as distribuições Linux funcionarão; um VPS é exatamente como um servidor real, exceto talvez pelo kernel. Então você tem que olhar para quais serviços você precisará executar; Eu pessoalmente executei um servidor web lighttpd com um banco de dados MySQL com aproximadamente 256 MB de RAM, e apache2 com um banco de dados MySQL com aproximadamente 512 MB de RAM, todos eles podem ser ajustados para que eles usem muito menos memória RAM padrão.
Eu posso dizer agora mesmo que a configuração padrão do Debian com apache2 e MySQL provavelmente não irá funcionar bem com 128 MB de RAM, mas isso não quer dizer que o Debian suga em ambientes com pouca memória, tudo que você precisa fazer é ajustar as configurações em ambos os serviços para usar muito menos memória. Tenho certeza de que o mesmo acontece com qualquer outra distribuição.