I can't agree more with your judgement. I've read all these three books and the fact is just like what you mentioned. CLRS and TAoCP use a lot of space to prove the algorithms correct(especially TAoCP, it even uses different ways to prove one algorithm) and that makes me feel dizzy. Perhaps I'm just a programmer not a computer scientist.
But I have to say that use some time to read CLRS and TAoCP is worthwhile. It will help u know more about algorithms and avoid the condition that just know how but not know why.
I agree with your analysis. From my review of Skiena (http://www.mccaughan.org.uk/g/books/alg-design.html): "Put differently, this is a book for algorithmic engineers rather than for algorithmic scientists." And: "You really wouldn't want this to be your only algorithms book. It doesn't have enough in it, it doesn't go deeply enough into anything, and a certain amount of the bracing mathematical rigour that the book so conspicuously lacks is ... well, good for the soul, I suppose. So go buy Cormen, Leiserson & Rivest. Then, unless you're already an expert algorist, buy this one too."
EDIT: Though, that's not to say I wholly endorse CLRS. I think Knuth's The Art Of Computer Programming is more detailed and more mathematically rigorous than CLRS. Unfortunately TAoCP is multiple volumes, while CLRS manages to be a single (substantial) volume.