Сам /usr/bin/palemoon или newmoon - это вообще "прокладка", я его могу как угодно назвать - это никак не влияет. В их оригинальной упаковке - это вообще симлинк. У меня это С-ная программа, которая запускает palemoon-bin. Не ожидал, что на неё уже зависимость настроилась.
Можно поступить по-разному, вопрос, что правильние.