A menos que você realmente precise de telnet por algum motivo incomum, não use o telnet para isso.
O SSH pode fornecer o mesmo ambiente, mas fornece criptografia e muitos outros recursos úteis. Por outro lado, o Telnet não fornece nenhuma segurança, senhas são enviadas em texto simples. Certamente, eu nem consideraria permitir telnet fora de uma lan em casa ou outra rede segura.
Vários clientes do windows ssh estão disponíveis, massa sendo um dos mais populares. Não requer nenhum privilégio de instalação ou administração para usar.
Todas as distribuições linux virão com um servidor ssh, embora algumas (como o ubuntu) não o instalem por padrão. Instalar o servidor ssh empacotado pela sua distro geralmente fará toda a configuração para você, não é necessária nenhuma configuração manual, a menos que você queira alterar as configurações padrão (geralmente, para adicionar coisas como restrições de segurança). Já existem algumas perguntas sobre como proteger seu servidor ssh.
Os servidores Telnet também devem estar disponíveis para sua distro, mas, por favor, considere as alternativas antes de escolher essa opção.