Eu acho que um autoextrator é de fato a solução mais fácil para você e seus usuários, mas implica que todos os usuários tenham a mesma senha. Muitos utilitários ZIP suportam, incluindo 7-Zip (com AES-256).
Paquet Builder mostra uma boa GUI , mas não é grátis.