I have a smart co-worker who also likes Skiena's Algorithm Design Manual. I found that book to fluffy, though. But then I enjoy books like "Combinatorial Optimization - Polyhedra and Efficiency" by Alexander Schrijver.
(Not a beginner's book, but it has anything you ever wanted to know about P and NP.)
(Not a beginner's book, but it has anything you ever wanted to know about P and NP.)