The title says it all! Tools / utilities / games that I might not have heard about, but you can't live without?
pv  - progress bars in any pipeline. Very handy, but not well known. http://www.ivarch.com/programs/pv.shtml
watch - execute a program periodically, showing output fullscreen.
To watch the contents of a directory change, you could use
watch -d ls -l
If you're only interested in files owned by user joe, you might use
watch -d 'ls -l | fgrep joe'
htop  An interactive process viewer, basically a fancy version of top with easier nav/tool and fancy colors! http://htop.sourceforge.net/
Lyx  it's a great document processor to write lengthy papers that look great thanks to LaTeX. It has great support for equations, and allows you to write LaTeX directly if the functionality you need (i.e. Headers and footers) is not in the interface.
Don't know if it counts as it works on Windows and it's not that unknown. http://www.lyx.org
f.lux , a daemon that darkens the screen at night. There actually are Windows and Mac versions (with nice GUIs, too), but the program still fits your criteria. It's a little odd at first because the screen might turn yellow, rather than simply darken, at night. It works nicely, though. http://www.stereopsis.com/flux/
 - for a very nice GUI to comparing text files. Also works with many version control systems.
Dropdown termial from the top of the screen at a keypress, Quake style. http://yakuake.uv.ro/
 -- so many people type passwords un-necessarily
and some even push them at the command line in scripts!
There is also an on-line version  -- but, I am not sure if I'll trust it (maybe for test machines).
In response to the comment about password-less use of
public key authentication
It agree to the point and the following should be clarified.
Once you work out your security expectations, password-less public key authentication is a great help. http://www.openbsd.org/cgi-bin/man.cgi?query=ssh-keygen
A game: xmoto . http://xmoto.tuxfamily.org/
I've been pushing this one pretty hard since I came across it: Pandoc .
Pandoc is a Haskell library for converting from one markup format to another, and a command-line tool that uses this library. It can read markdown and (subsets of) reStructuredText, HTML, and LaTeX, and it can write markdown, reStructuredText, HTML, LaTeX, ConTeXt, PDF, RTF, DocBook XML, OpenDocument XML, ODT, GNU Texinfo, MediaWiki markup, groff man pages, and S5 HTML slide shows.
______ _ _ _ | ____|(_) | | | | | |__ _ __ _ | | ___ | |_ | __| | | / _` || | / _ \| __| | | | || (_| || || __/| |_ |_| |_| \__, ||_| \___| \__| __/ | |___/
ack  -- "better than grep", they claim, and it's true. http://betterthangrep.com/
autojump . It's the fastest way to move around in your filesystem from the command line. http://wiki.github.com/joelthelion/autojump
Bastet: bastard tetris . Basically it gives you the pieces you DO NOT WANT instead of any one at random. You will spend hours in the terminal trying to get at least 10 lines in a single game, or a session for that matter. http://fph.altervista.org/prog/bastet.html
Firewall Builder  is a GUI firewall configuration and management tool that supports iptables (netfilter), ipfilter, pf, ipfw, Cisco PIX (FWSM, ASA) and Cisco routers extended access lists. http://www.fwbuilder.org/
I use xosview  a lot. It's very lightweight and gives me a pretty good snapshot of what the system performance is like. It could have some more detail and I don't know that I need the INTs but the load/memory/disks graphs are indispensable. I don't know how "well known" or popular it is. http://xosview.sourceforge.net/
Seriously, someone hasn't said Lynx ?
How else would you search for solutions to your problems when you lose your GUI? http://en.wikipedia.org/wiki/Lynx_%28web_browser%29
ncdu  - ncurses based display of disk usage. http://dev.yorhel.nl/ncdu
unclutter. It hides the mouse pointer in X when you're not using it. Couldn't find a link off-hand, but it's in most distribution's repositories.
mc - file manager
dstat  – shows pretty statistics for disk, network, memory and CPU. I really like it when I'm load testing and diagnosing slowness. http://dag.wieers.com/home-made/dstat/
Someone mentioned Lynx, so I'm going to add Links http://www.jikos.cz/~mikulas/links/ It has support for gpm console mouse and can display graphics using framebuffer! So you have in terminal a real browser with some capabilities of modern browsers.
I like autossh  also :) http://www.harding.motd.ca/autossh/
mmv is old, but very useful.
Zim  is a lightweight, desktop-wiki. It makes taking and organizing notes quite easy. http://zim-wiki.org/
Probably btnx , a tool for customizing and tweaking every mouse button you have (great for mouses with tons of hot keys). Plus its all GUI based for those that are afraid of the command-line. http://www.ollisalonen.com/btnx/
GRAMPS. An excellent Genealogy software. Open Source, written for Linux. Easy to use, loads of features. And, it's Python!
I have abandoned it for a wed-based software called The Next Generation, but that's so the whole family can help out and look at the database. GRAMPS was way better though. I wish it could connect to a SQL database, that would be awesome.
iftop , console (ncurses) network traffic monitor http://www.ex-parrot.com/pdw/iftop/
vimprobable  - a lightweight web browser. http://vimprobable.org/
synergy  : Allows sharing of keyboard and mouse between computers over a network. http://synergy2.sourceforge.net
qataki  - shell script for Identi.ca/twitter handling. It's ideal for terminal env since it allows you to edit many options. I saw that somebody already mentioned f.lux so i want to mention redshift  too.
uzbl  is also on my list. It can be really good when you start using all of it's options in configuration. http://chr.tx0.org/qataki/
vimdiff  ftw. Love people's reaction when I introduce them to vimdiff after watching them diff a file. Might not be the biggest secret but many people are unaware of it. http://vimdoc.sourceforge.net/htmldoc/diff.html
GNU m4  macro processor to produce pages for web sites from templates as well as other, more traditional, uses with make and sendmail. http://www.gnu.org/software/m4/m4.html
Simplest interface, but who needs all that Amarok bloat anyway. http://wiki.xmms2.xmms.se/wiki/Main%5FPage
podencoder . It encodes video for iPod. http://code.google.com/p/podencoder/
Vifir - A charting tool for pilots.
e 0.02718 , a tiny commandline expression evaluator. I've been using it so long I'd forgotten where it came from. Very difficult to Google. http://code.google.com/p/quodlibet/
TreeLine . It's the best personal database / list maker / virtual blotter I've ever seen. It may be the best personal database possible. There's now a burgeoning category of "personal information management tools"; this is still the best one. If you haven't tried it before, try it now. (Note: there's also a Windows version nowadays, but it started out as Linux software. If BSD is your primary OS, there's also a FreeBSD port, but I can't vouch for its quality as I've never tried it.) http://treeline.bellz.org/