I like the format of deb-a-day, but I want to list many of the programs I use and a description on how they work will take too long. I'm always open to suggestions if you know of something better. Nearly everything I use is a command line interface and I'd like to keep it that way. If something is primarily a GUI, I'll note that below. I'll try to stay away from programming tools and libraries for this round. It's a lot more work to list all of those.
- abcde - cd ripper to flac/ogg/mp3 (with lame)
- apcupsd - APC UPS daemon
- aptitude - better than vanilla apt-get
- aspell - better than ispell
- auctex - great when you're writing TeX in Emacs
- audacity - useful for manipulating wav files (GUI)
- bitpim - read/write to my cell phone (LG vx8300) (GUI)
- cccc - C/C++ code counter
- chase - simple utility to follow symlink chains.
- chktex - find typo erros in LaTeX
- clive - download files from youtube, google, etc
- cclive - C++ spin off of clive
- curl - for when wget just won't do
- dia - diagram editor
- diffstat - generate graph of diff changes
- djview4 - Viewer for DjVu image format
- dlocate - faster than dpkg -L and -S
- dmidecode - Dump BIOS information
- doxygen - Better than javadoc and available on C, C++, Java, Python, etc
- dpatch - Patches for debian. I may switch to quilt
- dsniff - Sniff network traffic
- dvd+rw-tools - best (only?) way to burn DVDs in GNU/Linux
- dvdbackup - rip DVDs but not transcode
- dvdisaster - generate ECC data for DVDs to try to mitigate failures
- emacs - nothing is better than GNU Emacs (flame on!)
- encfs - userspace encryption
- etckeeper - keep revision control on /etc by using hooks in aptitude
- evince-gtk - modern PDF viewer which is a good replacement for xpdf
- extract - like file(1) but provides more information
- festival - Speech synthesis system.
- festvox-* - Additional voices for festival
- ffmpeg - media player, encoder, and transcoder
- flac - lossless audio codec
- gddrescue - tries hard to recover data from recordable media
- genisoimage - fork of mkisofs
- gimp - Image editor (GUI)
- git - fast, distributed revision control
- gnash - Flash movie player that sometimes works
- gnucash - finance tracking (GUI)
- gnulib - portability library that's useful with autoconf
- gnupg - free PGP
- gnuplot - plotting program
- gnuserv - attach to an already running Emacs instead of starting up a new one
- graphviz - automated graph drawing tools
- gv - postscript/PDF view
- hdparm - tune hard disk
- icedax - fork of cdda2wav
- iceweasel - Debian branding of firefox (GUI)
- imagemagick - image manipulation
- kernel-package - build kernel images the Debian way
- keyjnote - eye candy heavy PDF viewer (GUI)
- lacheck - simple syntax checker for LaTeX
- lastfmsubmitd - last.fm submission daemon
- latex-beamer - LaTeX class for making nice presentations
- lmodern - nice LaTeX font
- lrzsz - tool for (x|y|z)modem
- lsof - list open files
- lynx - browser
- memstat - virtual memory usage display
- memtest86+ - maintained (or relatively) fork of memtest86
- mimms - mms:// stream downloader but it doesn't always work
- mplayer - most advanced audio/video player in Linux
- nitrogen - small/simple desktop background changer (GUI)
- nlkt - non-linear keyboard typing program
- normalize-audio - normalize volume
- noweb - best literate programming tool I have found that's language agnostic
- octave - similar to (and tries to maintain compatibility with) matlab
- openbsd-inetd - an inetd that will actually listen on just localhost
- openclipart-openoffice.org - Openclipart project for use with OpenOffice.org
- openntpd - NTP daemon from OpenBSD
- openoffice.org - Office suite that can read/write Microsoft formats (GUI)
- openssh-blacklist - Blacklist old vulnerable OpenSSH keys
- openssh-blacklist-extra - Blacklist old vulnerable keys
- p7zip - 7zip archiver
- patch - apply a diff
- pbuilder - build Debian packages in a chroot
- pcal - generate full page postscript calendars
- pcregrep - grep with perl compatible regex
- pdf2djvu - PDF to DjVu converter
- pdfjam - PDF manipulation utilities
- pdftk - PDF manipulation utilities
- perceptualdiff - perceptual image comparison
- postgresql - full SQL database
- pspresent - postscript presentation tool (GUI)
- psrip - rip images from postscript files
- pwgen - generate passwords
- quilt - interact with series of patches
- recordmydesktop - Nice way to create an ogg theora video of your X session
- rsync - fast remote copy
- rubber - build LaTeX documents by running as many times as needed
- screen - multiplex terminals
- shntool - SHN utility which is useful with etree music archives
- slime - best way to hack lisp in Emacs
- smartmontools - view SMART attributes of your hard drives
- socat - multipurpose data transfer relay
- sqlite - standalone, single user SQL database self-contained in a file
- texlive - teTeX is dead but long live Texlive
- tidy - tidy up HTML source
- unison - bidirectional rsync
- valgrind - memory debugger
- vim - for when you have to use vi
- vlc - media player (GUI)
- weather-util - obtain weather conditions
- wget - get files from ftp/http sites
- whizzytex - automatically display LaTeX output formats while editing in Emacs
- wodim - fork of cdrecord
- xcompmgr - example implementation of managing compositions in X
- xmonad - tiling X window manager
- zsh - shell with more features than any other