Удаление программ
 

Я скачал программу в виде *.tar.gz (кажется это называется "тарболл"?).

Распаковал, откомпилировал, всё заработало. Всё ок.

НО! Мне эта программа не понравилась. Как её корректно удалить?

Корректно -- никак. Можно попробовать make uninstall в исходниках, или изначально ставить так проги только в /opt или /usr/local. Но RPM и DEB придумали именно для того, чтобы избежать подобных вопросов.

Абсолютно корректно удаляет make uninstall (разумеется, под рутом). Если вы уже удалили исходники, распакуйте их снова, ./configure, а затем make uninstall.
Для создания rpm пакетов можно пользоваться checkinstall, правда он не всегда срабатывает. (Взять можно на www.linuxcenter.ru/games ).
После ./configure, make, набираем checkinstall -R, вводим информацию, далее ставим по указанному в конце пути (если, конечно, не было ошибок).

make uninstall "абсолютно корректно" удаляет, только если автор это предусмотрел. Для всех систем. Привести примеры, где это не работает? Их тьма (:))

У меня DEB и я не могу найти DEB пакеты некоторых прог, но у меня есть исходники.

Дык это. Вот я набираю make install и прога инсталлица. Куда?

а куда Аллах пошлёт. Обычно, в --prefix. Если указал. Если нет -- то может в /usr/bin. А может в /usr/local/bin. А может в /opt/proga. Хез. Попробуй сказать make uninstall таки. Если не поможет -- советую поменять церковь (:)) Т.е. сидеть там, где есть или DEB, или RPM. Сэкономишь массу нервов.

Если не получается удалить прогу через make uninstall, то можно просто поискать ее файлы на диске вручную и удалить.
Делается это так:

индексируешь файлы.
slocate -u
ищешь прогу.
locate prog_name
и удаляешь файлы вручную.

Правда при таком способе удаления надо точно знать что делаешь, иначе могут быть неприятные последствия для системы,
типа что-нибудь полетит :(
так что как говориться, на свой страх и риск.
Или ставь проги из rpm, если у тебя rpm-based дистр.