I second you. I have found Steven Skiena's "The Algorithm Design Manual"[1] to be a great book in this regard. Of course, like you say, CLRS remains an excellent reference.
I think Skiena and CLRS are complementary, each compensating well for the limitations of the other. If you were going to have exactly two algorithms books, I'm not sure I can think of a better pair.