I've read the first three, and attempted every single exercise (besides the few he marks as "suggested research problems"). It took me four years to finish, and I had a MSCS when I started. The first volume is probably the most math-intensive, but also the easiest, since a lot of the math is review. V1 is split into two parts: a pure math half, and then a programming half. All of the programming examples and exercises are done in a custom assembler that he calls MIX, but you can find emulators online to run your programs. I've read CLRS and Knuth and I definitely enjoyed Knuth a lot more - there's just something about his writing and exposition that makes the books compelling. They dare as well as entice you to understand them. It's not really as proof-heavy as CLRS IMHO, and TAOCP covers different ground that CLRS does; the only real overlap there is that volume 3 covers sorting algorithms.
If you like the math in Volume 1, or find yourself having difficulty with it, Concrete Mathematics is a good companion (though also challenging). It goes into greater depth on some of the topics in Chapter 1 of TAOCP and some additional directions. It started as a course aimed at providing the mathematical basis for going into TAOCP.
