An absolute gem is FreeMind which is a java app (don't let that put you off

) and is a very fast and easy to use mind mapping application. I had tried using a couple of them before and always thought they were more effort than they were worth, but I found that using FreeMind I very quickly was able to get my thoughts down and organised. The killer feature that made it for me is that you can control everything via simple and logical keyboard shortcuts which speeds things up no ends and means that the application does not get between you and what you are thinking about.
Would cross platform stretch to online services too? If so then Hiveminder is a wonderful way of sorting collaborative todo lists

The handy thing there is that it will talk to IM services and twitter so you can interface with it in many ways.
Another killer app for me, as I am often working with more than one machine, is a program called Synergy which shares your keyboard, mouse and clipboard (text only) with another machine. Simply load it up (the Windows version has a gui and the linux version has a gui called quick-synergy) and then you can simply move your mouse cursor from one machine to another and copy and paste from one machine to another it really is a thing of joy

For me it means that I get into work plonk my linux laptop down on the desk next to the work provided windows one and I can have the best of both worlds from one keyboard and mouse without interrupting my workflow

Technically this may not be classed as a productivity app but it has probably saved hours of lost productivity for me just swapping to keyboards and e-mailing stuff between machines etc.