About the tools already mentioned, I used (long ago) ollydbg and IDA. Several others too: w32dsm (or something like that, a debugger, older than olly IIRC), softice/winice (ring 0 debuggers for windows up to XP I think. There was rr0d, Rasta Ring 0 Debugger that was doing the same for windows, linux and freebsd, but never tried it)... those are only for debugging.
Then there was a shitload of resource analyzers, tools to guess compiler or packer used on a specific binary... that I don't remember well.
And of course, hexadecimal editors. My favorite back then was, without a doubt, WinHex. I even used it to recover deleted files :)

I'm no longer in reverse engineering, since I now usually have the source code. Except when I wan't to have fun, but I rarely play with those things now.
Still, I use some tools that fill the holes on linux, because I write code and it's a need to have some insight.
Quality is usually lower, but hey... For winhex, there is wxhexeditor.
For debuggers, I usually use gdb, with the cgdb frontend. I tried the *cough* GUI mode of GDB: it sucks. Really. Maybe someday I'll write my own frontend, that's something I have in mind since long, but then I think I'd try to learn to use LLDB before, since I'm pretty sold to most of LLVM suff: clang is so much better than gcc, libc++ just kills libstdc++, so maybe LLDB is better than GDB too.

Radare2 in on my TODO list of stuff to try since long, too.