Добавлю
devilspie - очень полезная управлялка окнами.

Deluge для торрентов
gPodder для подкастов
digiKam для управления фотографиями

тоже регулярно использую: amarok, bash, cmake, firefox, gcc, gajim, hg, k3b, kate, konsole, latex, mplayer, svn, qmake

OpenShot Video Editor - простой видео редактор, например для подготовки файлов перед заливкой на видео обменники.

ncdu - ncurces программа для удобного анализа и подчистики места на диске
qstardict - легкий и быстрый словарь на Qt, "понимает" словари в формате Stardict

Geany - шустрый редактор кода: подсветка синтаксиса, поддержка проектов...
Nexuiz - супер стрелялка

WebmonX - следилка за изменениями сайтов с настройкой тех фрагментов, за которыми осуществляется слежение.
FatRat - самая, на мой взгляд, вменяемая качалка файлов.
Kid3 - редактор аудиотэгов.
Audex - аудиориппер.
KeepassX - менеджер паролей.
QPxTool - штуковина для проверки качества записи CD.
DeaDBeeF - аудиоплеер а ля foobar.
zNotes - заметки на полях.
FBReader - читалка книг.
MyRuLib - библиотекарь для либрусека и флибусты.
Vacuum IM - новый jabber клиент.
Qwit - twitter клиент.
Namebench - тестер dns-серверов.
CeltX - редактор для сценаристов/драматургов, сделанный на движке Mozilla.
ASTranslator - онлайновый переводчик на движке Google.

Это чем я пользуюсь, постоянно или периодически.

mkvtoolnix -- аудит и редактирование матрёшки (*.mkv)
mocp -- клиент-серверный консольный аудио-плеер
yakuake эмулятор терминала (в стиле выпадающей консоли из quake3) для кде

eyeD3 - для просмотра и редактирования id3 тегов (консольный)
mp3info2 - для просмотра и редактирования id3 тегов (консольный)
QPxTool - прога (на qt) для тестирования записанных дисков

Kile- LaTeX ориентированный редактор, latex>{dvi,ps,pdf}конвертер
LYX - что ты видишь, то ты получишь редактор
Jmol, atomeye вьювер атомных & молекулярных структур
Kb3 - писалка, грабер и т.д.
Kate- KDE based среда разработки
nmap - network scanner

Flush - для торрентов
KeepassX - менеджер паролей. +1
FBReader - читалка книг. +1

rawdog — RSS-аггрегатор, читает фиды и пишет их в один (большой) html-файл. Просмотр в любимом браузере. Обновление через cron или ручным запуском.

Мое, из того, что еще не назвали.
GNOME Do — лаунчер с кучей плюшек.
GoldenDict — оболочка для словарей с функцией перевода выделенного текста.
Guake — выпадающий эмулятор терминала на GTK.

mcabber - консольный джаббер-клиент
pwgen - консольный генератор паролей
scrot - снималка скриншотов

eiskaltdc - dc++ клиент
atool - для работы с любыми архивами
sleuthkit - восстановление данных
foremost - восстановление raw данных
meld - сравнение файлов и каталогов
partimage - в отличии от dd, создает образ фактического размера данных
gammu - для работы с моб. тел.
clive - качаем с youtube
exfalso - редактор тегов mp3 (имхо лучшая)

chromium
conky
все и так их знают, так что и описывать нечего

gXNeur - типа Keyboard Ninja or Punto Switcher
CheckInstall - позволяет из сырцов создавать DEB пакеты.
extundelete — программа для восстановления данных в ext4.
Btnx - прога по настройке клавиш мультимедийных грызунов.
XSplash Background Settings - замена фона экран приветствия (после GRUB`a).
gCue2tracks - утилита для нарезки лослес альбомов и редактирования тегов к ним (*.ape, *.flac, *.wv, *.mp)

Выше уже упоминалась eyeD3 (консольна утилита) - лучшее что я видел для редактирования id3 тегов (в особенности когда извращенецы заталкивают их в *.ape файлы).

awesome — тайлинговый WM с Lua-конфигами,
Vim — в рекомендациях не нуждается =),
Urxvt — минималистическая консолька с поддержкой Unicode,
tmux — консольный мультиплексор, современная замена screen-а,
mcabber — для жаббера/гуглотока,
cmus — иногда музыку послушать,
zsh — лучшего файлменеджера не существует =),
slim — минималистический логин-менеджер для Иксов.

Wyrd - неплохой консольный календарь/органайзер.

Хм, ничего оргинального:
Gmail Notify - почту проверить
Wine+Fireworks - порисовать/поправить изображения
Shutter - скриншотик сделать
EisKaltDC - что-нибудь раздать
Furius ISO Mount - что-нибудь образное подключить
Phoronix Test Suite - письки что-нибудь померять

Может стоит обновить пост, добавив вниз спойлер с рекомендациями остальных?

sdcv - консольный интерфейс словаря StarDict. У меня в комплекте 38 словарей от Лингвы.
ncmpcpp - лучший, на мой взгляд, front-end для музыкального проигрывателя MPD.
workrave - программка позволяет работать и не уставать. Блокирует экран и ввод каждые N минут, заставляя отдохнуть.
xmind - MindMap manager (рисовалка для карт памяти)
gtick - метроном (штука что бы отбивать ритм при игре на музыкальных инструментах). Но недавно купил метроном в виде электронного девайса.
jdownloader - лучшая качалка со всяких файлообменников вроде rapidshare, depositfiles и других. Рекламу смотреть не надо, ждать тоже.

dockbarx - неплохой док, легконастраиваемый и простой.
FCEUX - для любителей 8-битной старины. Эмулятор NES.

Calibre -библиотека и читалка. Поддеживает всеми наш любимый fb2.

Filelight - необычный отображатель занятого места на диске.

tilda - выпадающий эмулятор терминала
mednafen и mednafenfe - эмулятор множества игровых консолей и фронт-энд к нему. Ностальгия по детству и dendy :)
qutIM - icq и jabber-клиент
rtorrent + rtpg - люблю попиратитьпокачать с торрентов
mpd + ncmpcpp - как по мне - лучший выбор для прослушивания музыки
emacs - считаю, в представлении не нуждается
openbox + tint2