I suspect your question will prompt answers from Monks knowledgeable about Net::SFTP and, more generally, about ciphers (/me is definitely not), but a non-perlish solution may be worth considering if you don't get a silver bullet here:

Fire the customer! Life is too short to deal with customers who don't trust their experts.