For me CLRS was a book that explained concepts in an easy to absorb fashion. For example the dynamic programming chapter is top notch.

While the "War Story" section in Skiena's book gave a great perspective of application of the theory.