NOTE: When adding useful contributons to this thread, please just batch a few programs into one single post, so that future referals to a certain program mentioned in the thread are easier to follow.
Also please ONLY add freeware programs!
It's the windows media player but heavily modified and able to play damn near any video format you throw at it, especially when used with the next entry
http://sourceforge.net/project/showfiles.php?group_id=82303&package_id=84358
This is a very nice little codec pack - it has all the codecs you need and none of the extra crap that some of the enormous packs have. Also, you can find "quicktime alternative" and "realplayer alternative" here, which will let you play .mov or .ra files with media player classic, instead of having to install the bloated quicktime or realplayer themselves.
http://www.k-litecodecpack.com/
is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, mp3, ogg, ...) as well as DVDs, VCDs, and various streaming protocols. It can also be used as a server to stream in unicast or multicast in IPv4 or IPv6 on a high-bandwidth network. If Media Player Classic should ever fail, this player might still be able to do the job. I've been able to pretty much play every damn media file in this thing. It isn't as purdy as other players, though.
http://www.videolan.org/vlc/
For those pesky binaries with no .cue
http://www.weethet.nl/english/download.php
For mounting (and creating?) virtual CDs
http://www.daemon-tools.cc/dtcc/portal/download.php?mode=ViewCategory&catid=5
For opening and working with CD images and lots more
Freeware up to 1.0
http://www.smart-projects.net/isobuster/