Is there a "upon first login, create a ssh-key pair" option? Or should I just make the user generate a key-pair and have them send me their public key?
Se for necessária uma senha, como eles farão o login pela primeira vez?
Dadas as suas restrições, parece que você terá que enviar uma chave pública para você. Dependendo de quão habilidoso você espera que os usuários sejam, você pode querer fornecer a eles um utilitário que possa ajudar a gerar isso para eles. Caso contrário, basta executar o comando ssh-keygen e enviar o arquivo id_rsa.pub que ele gera.