If you have a setup with 2 or more computers with seperate screens on your desk, Synergy is quite possibly the best productivity tool around. It allows you to use one keyboard and mouse to control all of the computers on your desk. It's cross platform, so I have one keyboard and mouse and control both of the machines on my desk - even though one is windows and the other runs linux. Synergy sends the key presses and mouse moves to the other computers over the network. I've been using Synergy since ~2005 and I couldn't live without it these days.
The client of the future, Irssi is a very handy little irc client. Now available on windows as well as its native Linux.
A great little media player, seems to play anything you can throw at it. Comes highly recommended.
Easy encryption of any important data, such as customer data, or anything else that needs to be encrypted. Multi-platform support, even supports encrypting usb keys! An all round generally useful application.
My browser of choice. Some people love it, others hate it. Opera is my normal day to day browser, I tend to run the weekly builds from the Desktop team. They have a great attitude to software, releasing public weekly builds to give people who want to a chance to try the new features and spot some bugs. So many features out of the box, and yet very little overhead.
Mumble is a voice chat application much like Teamspeak or Ventrillo. The difference with Mumble is that it is Open Source and has some really nice features the other two lack. Like showing an in game overlay so you can see who is in the channel with you and who is talking. As well as an ability to quieten the rest of your applications which might be using the sound card whilst someone talks. This allows you to listen to music and not miss what anyone says at the same time - really handy.
A superb little program which adjusts the colours used by your screen at night. It makes using your computer at night much less painful on the eyes. The only time you notice it doing it's work is when you turn it off temporarily or try and do some graphic design work of an evening. It's a sign of better software, it works without interfearing with your day.
My linux desktop currently runs a minimal Debian Lenny install.
Wmi and Wmii are tiling window managers, an alternative to something like Gnome/Kde. It's probably best to see the screenshots on the Wmi/Wmii website to get an idea of how they differ. I don't have floating windows, everything is tiled and displayed at once. My work usually involves me having many terminals open, so it's great to see the whole of each terminal at once, without having to flick between them.
Screen is a superb little application to allow you to keep sessions open on machines and allow you to disconnect and reconnect to them. This is probably best explained with an example, I run irssi (mentioned below) on a remote machine in a datacentre. Rather than run it whenever I want to jump on IRC, I leave it running in a screen session. This allows me to reconnect to it from any location, at any time. So I can catch up on anything that was said in my absence. I couldn't live without this great little tool.
An alternative file browser to Nautilus that comes with Gnome. Its not really possible to use Nautilus without Gnome, so a similiar replacement is Thunar. Thunar is part of the Xfce project.
If you ever need a simple no nonesense cd encoder, abcde is for you. Chuck the CD in your tray, type abcde in a terminal, all done.
Textpad is a very useful and very customisable text editor. Its not freeware, but well worth the money.
Putty is a really nice terminal environment, once combined with the cygwin it makes for a very nice terminal and working environment. Cygwin is great for those linux terminal applications you are used to using which just don't exist on Windows. GNU applications like tail can be very useful in a windows environment every so often.
This is a handy music player, at first the rather basic UI put me off. I tend to run music players purely in the system tray and use hot keys to control them. So the UI is irrelevant. foobar is lighter than most other players and is worth a try. :)
Paint.Net is handy for all those occasions when you would use the regular mspaint, but need something a little bit more. It is full of features, but not a huge drain on resources. For my basic image editing needs, its perfect.