Operating Systems and Live CDs/DVDs:
Gentoo Linux: probably the last step before linux from scratch but it does work nicely when properly compiled. best left to advanced and professional users
Debian linux: an old and usually very stable distribution, you can do a lot with it, but better suited for advanced users.
Ubuntu: Easy to use linux that made linux probably more famous then any linux before.
User Basics
OpenOffice: A lot like MS-Office only without ribbon and free
Mozilla Thunderbird: The alternative to Outlook and Windows Mail
Mozilla Firefox: For all those that don't want Internet Explorer, easy to use and tons of plugins.
Opera Webbrowser: The browser that practically invented Session Managment, big, not fully compatible with everything, but if you want to keep your forum threads open there is no better choice.
CCCP Codec Pack: I'm not sure if this codec pack is legal everywhere so use at your own risk. Includes Media Player Classic Home Cinema, good alternate to the Windows Media Player.
VLC Player: One of those Players that plays almost everything. My favourite alternative to Windows Media Player.
Irfanview: A nice Image viewing software. Small yet can show you almost every pic out there.
Intermediate Software: You don't need it but it helps
The Gimp: the alternative for all those that don't need Adobe Photoshop and only want to do small stuff.
Skype: The program that probably invented Voice over IP, or just calling over the internet.
7-zip: Probably the easiest free program there is for managing archives like zip, rar, ... it knows them almost all.
Speedfan: A small programm that allows you to check your system temperatures, doesn'T work with all models so handle with care.
Sysmetrix: This tool can show you CPU, Ram, Swap and hard disk usage, it has a lot of other functions too if you want. have fun picking one of the many skins.
Advanced Software: some of the things here can mess your pc up if you don't know what you are doing.
Testdisk and PhotoRec: Datarecovery made easier, good free tools, but watch out, with testdisk you can destroy your harddrive just as easily.
ImgBurn: if you need to make an image.
Portable-apps: if you want to take your own programs everywhere on your USB drive, portable apps is the answer.
Sysinternals: The most common programs from here you are likely to know are process explorer and autoruns.
FileZilla: nice calm FTP Client.