nc: Along with dd it can do wonders in data transfers. We can cloned harddisks/partitions piping nc, gzip and dd together.
dvdisaster: It is really nice tool to create error correction code of CD/DVDs. The ecc occupies much less space then actual disk and even when both ecc and original disk are corrupted (a little) we can still get original data back.
htop: It is way cooler then top as it uses ncurses to show things in nice colors and supports mouse.
tcptrack: It can be used to see live tcp sessions as th4y are getting created and closed. It can sort connections by speed. So you can see where is most of the bandwidth going.
iptraf: It can be used to monitor lot of network interfaces at once to see how much they are being used.
fdupes: It can help in finding duplicate files.
mail-notification: It gives nice pop-up with sound near notification area when new email comes to any of the configured accounts.
kompare: It can give visual diff of two files. You will have to use it once on two similar text files to really understand what I mean by visual diff. My favorite is to compare zone files of primary and secondary DNS to ensure they are consistent.
convert: It is very useful in converting from one image type to another. Specially to eps for Latex documents.
dos2unix / unix2dos: These help in changing files ending with '\r\n' to '\n' and vice-versa. Life saver for cross-platform developers.
indent: If you use vim for coding and do not want to indent some code file by hand. This is really good.
Doxygen: For generating documentation if written in javadoc files for source file in any language.
gftp: This is graphical client for ftp, ssh, http file transfers. It allows resume and asks for conflicting files whether they should be overwritten, resumes, skipped etc.
FileZilla: Similar to gftp above. But it also allows parallel connections to various sites.
Wireshark: I cant say that it is not famous. But it is extremely useful tool that I have used many many times to debug network problems. It is a must for every network administrator.
phpMyAdmin: It can be used to manage MySQL database using web browser from any where very easily. Best part is export options to various formats and easy backup and restore options.
phpPgAdmin: Similar to phpMyAdmin, although not as powerful as phpMyAdmin but it does make life easier.
p7zip: Really nice compression and very helpful in case formats zip / rar are blocked for some reason.
k3b: Really good at burning CD/DVDs. We can burn ISO images or create multi-session data DVDs. We can control what OS support is necessary and whether to use extensions like joilet, rocket ridge etc.
kile: Really nice editor for LaTeX documents. It supports good shortcuts for making dvi, ps, pdf etc and compiling and previewing only selected portion of text