Em um sistema Debian (ou em uma distro derivada do Debian, como o Ubuntu), a possibilidade de múltiplos pacotes provendo a mesma funcionalidade é dada pelo sistema de alternativas. O link explica como o sistema funciona e como configurá-lo. Embora isso não elimine a necessidade de reiniciar o Firefox ao mudar entre os dois, ele irá pelo menos cortar a parte de desinstalação e reinstalação.
As distribuições baseadas em RPM devem fornecer funcionalidades semelhantes, mas não estou familiarizado com o funcionamento ou com as ferramentas que precisariam ser usadas para manipulá-las.