Here's what I've discovered as being useful for experimentation and prototyping:
555 - this chip is never going to die. It's very convenient to be able to change the time constant by swapping a cap or resistor.
Schmitt trigger inverters and NAND gates - useful for oscillators, gated oscillators and buffering.
"linear" inverters and NAND gates - useful for driving crystal oscillators
4017 - very useful for dividing a clock signal down by a small number or generating a short sequence.
counters (like the 4020) - useful for dividing a clock signal down by a larger number.
shift registers - useful for microcontroller I/O expansion. I generally turn to a '595 if I need to expand a microcontroller's output capability.
4066 - analog switches - can't do that with a microcontroller
4046 - V-F converter, PLL frequency multiplier
multi-unit buffer/line drivers (74HC125, 74HC240, et. al) - useful for a quick-n-dirty multi-line logic probe and general buffering. Also popular in BEAM robots.
Some things I haven't found generally useful: discrete flip-flops, OR and AND gates, BCD decoder/drivers, addressable latches, decoders/demultiplexers. When an application gets complex enough to need these components, it's usually more efficient to start using a microcontroller.