Eu vejo duas maneiras de ver isso.
Um é direcionar os Linuxes mais populares, fornecendo pacotes nativos para cada um, entregando pacotes em ordem de popularidade. Alguns anos atrás, isso significava fornecer RPMs para Linuxes do tipo Red Hat primeiro, e depois, conforme o tempo permitir, a reconstrução do RPM de origem para cada Linux menos popular baseado em RPM. É por isso que, digamos, o Mandriva RPM é geralmente um pouco mais antigo que o Red Hat ou SuSE RPM. Com o Ubuntu sendo tão popular nos últimos anos, você pode querer começar com .deb e adicionar RPM depois.
O outro é tentar direcionar todos os Linuxes de uma só vez, o que é o que aqueles que fornecem tarballs binários estão tentando. Eu realmente não gosto dessa opção, como um administrador de sistema e usuário final. Esses tarballs espalham arquivos por todo o sistema em que você os descompacta, e não há opção mais tarde para detalhes como desinstalação, verificação de pacotes, upgrades inteligentes, etc.
Você pode tentar uma abordagem mista: pacotes nativos para os Linuxes mais populares, além de tarballs binários para Linuxes excêntricos e administradores de sistemas antigos que não gostam de gerenciadores de pacotes por qualquer motivo.