Windows: Alt+space, [n, x, s, m] (n for minimize, x for maximize, s to change size. s, then arrow for which side of the window to drag, then move with arrows. m for move, also with arrows). Ctrl+esc, menu bar. windows key+e = explorer, windows key+r = run dialog. alt+print screen = system preferences. (Haven't used windows in years, so not sure if these shortcuts persisted through Vista and 7. I hear they did)
OS X: First, get Quicksilver. Seriously. Other then command+tab to switch apps which everyone knows, command+` (tilde key) switches windows within apps. I'm surprised how many people don't know that. Also, an awesome shortcut is Command+tabbing to a minimized window, then before releasing command, press down option, then let go of command while holding down option. That restores the minimized window and switches to it, really not bad after you get the hang of it. command+m minimizes. ctrl+f2 (might need to add 'fn' on laptops) puts the selection in the menu so you don't have to use the mouse to select it.
bash: ctrl+r is invaluable. that will do a reverse search through history on whatever you type next. only caveat: once you leave the search mode, you'll actually be in that place in history, hitting up will go back even further. I usually run an empty command (like echo) to get back to the bottom. Hitting meta (esc in my case), then dot inserts the last argument of the previous command. Great for edit,execute cycle. i.e. $ vi script.py $ ./[esc, .] running '^str^strb^' in bash will run the previous command, replacing str with strb. !! is previous command, !!:0 is first token of previous command (usually the binary running), !!:1 is first arg, etc.
If you use zsh (and you really should. It is better than bash in almost every way), you can just ctrl-C to get out of searches.
Some good stuff: http://grml.org/zsh/zsh-lovers.html
Enso is interesting alternative to launchy on Windows. It's no longer in active development. http://humanized.com/enso/launcher/
Using the lua config I changed a bunch of the key bindings so that the entire environment behaves like vim. I can easily change windows using the vim directional keys, which are second nature by now. I never lose windows behind other windows.
After a few days in this environment you start looking for apps that provide a keyboard interface to all their functionality so you can throw away your mouse entirely.
Vimperator is a good example. Also, I use irssi (http://irssi.org/) for all chat and instant messaging. We modeled the chat interface for ShopTalk (http://shoptalkapp.com) after irssi for exactly this reason.
dwm is also good, as are dmenu, screen and tmux.
EDIT: StumpWM video http://www.youtube.com/watch?v=tKt_rVO960Q
For the browser I usually use a mix of firefox's "mouseless browsing" and search with ' key.
The shell is bad for copy/pasting with only the keyboard. Even if ctrl+alt+c/v copies and pastes, selecting without mouse is really troublesome. I run shell inside emacs.
For changing desktops, I have hotkeys ctrl+alt+1/5 for each of my 5 desktops. I usually keep 2 windows maximized at once so I'm always at most 2 (usually just 1) key presses from any window (instead of following an alt+tab app cycle or a alt+ctrl+arrow desktop cycle)
pretty much everything else you need to do can be done inside of emacs.
Because I work with tools where using the keyboard shortcuts until they become reflex is an option, rather than only occasionally using programs and hoping they're "intuitive" enough to use by looking for what I want to do and pointing at it.
Because using language is more expressive than pointing at things all day.
Because you can't refer to something by name with a mouse unless it's already on a menu. (Well, mouse gestures could be considered an attempt to do this, but the set of "letters" is very limited.)
When a task is primarily spatial (typically, graphical editing; I'm not a gamer), I use the mouse. That's about it.
* http://www.amazon.com/Kensington-Expert-Optical-Trackball-64...
All I use it for is moving mail into folders without the mouse (F3, space, per(personal folder gets auto completed), enter, next!)
Really wish Gnome would throw in a feature that auto-maximizes windows like the other two managers I mentioned do.
How do you deal with rollover menus and seeking with a video player (on youtube and such) without a mouse?
No mouse required. Try it. Love it.