nedit - Free multi-purpose text editor. X Windows based but will run on Windows using...
cygwin - Free Linux API for Windows. Lets you run a whole bunch of UNIX things on Windows. Originally a RedHat project, so it's based on RedHat's package system. Handy especially for running SSH (secure shell) on Windows (a necessity if you're using VNC as VNC is not secure, unlike Remote Desktop).
PRTG - "PRTG (Paessler Router Traffic Grapher) is an easy to use Windows software that monitors bandwidth usage and other network parameters via SNMP" - i.e. you can graph bandwidth on any devices supporting SNMP. Especially handy for people with cable modems as you can monitor throughput on the modem without including internal LAN traffic. Free in a cut down version that monitors one device at a time.
TightVNC - Another VNC app. Uses compression to reduce traffic. Not as good as Remote Desktop, but useful in it's absense.
Miranda IM - Free open source, multi-protocol Instant Messenger. Supports MSN, ICQ, AIM, Yahoo, Jabber and others.
Yahoo! Companion for Mozilla/Firefox - Free unofficial version of the Companion toolbar for Mozilla/Firefox. Especially useful for Yahoo's Bookmarks feature which means you can get to your bookmarks anywhere in the world either through their Bookmark web page, or using the Companion toolbar on IE(with the official toolbar) or Mozilla/Firefox (with this unofficial version).
JDiskReport - Free disk space grapher/reporter. Java based and works on many platforms.
Auction Sentry - Auction snipe/auto-bid tool. Not free (though there is a trial period), but could be worth it if you really want to win those auctions. Doesn't risk your details on 3rd party servers, but instead does the bidding from your PC. Requires PC to be on and Auction Sentry running at the time the bid will be placed. Sniping works better with broadband.
Daemon Tools - Mount ISO images of CDs and DVDs, without having to burn them to a real disc. Handy for testing images. Emulates copy protection.
Winamp - Media player (works best with audio, MP3/WMA/etc). Winamp 5 recommended.
Cartes du Ciel/Sky Charts - Free sky chart astronomy software.
SpamSource - Plugin for Outlook to report spam to SpamCop. Available in free or pay versions, but the free version works fine enough.
Renamer - Free and powerful file renamer.
Coppermine - Free Photo Gallery software for websites. Requires a web server with MySQL, PHP and either GD or ImageMagick.
Xteq Setup - Tweak tool for Windows.
ClearType Tuner - Microsoft's ClearType tuner for Windows XP. Especially handy for users of TFT monitors.