Eu ficaria surpreso se sua empresa de hospedagem oferecer o Debian 6 imediatamente.
Em qualquer caso, não deve importar muito, já que o Debian usa o método 'rolling release', o que significa que a atualização é simples de atualizar: -)
Em outras palavras, vá em frente e comece com 5, porque você deve poder atualizar para 6 facilmente.