It depends on what you want. I've only read the first volume so far, but I would say that it's definitely appropriate for an intro to CS since you have the math background. I would definitely not recommend it to most people since the math is pretty dense and not all necessary (though very interesting). If you're familiar with combinatorics and stats, then it won't be too bad.
As a CS book, it teaches a lot of good CS concepts and techniques very thoroughly, and it analyzes the performance of algorithms very precisely. You'll not only use Big O notation, but you'll also figure out some of the constants. So, if your interest is in computer science proper, then this is a great introductory book.
On the other hand, if your goal is to be able to write programs, then definitely jump into using a language. Go find a book on a language and just start using the language to solve problems. After you get past the basics of programming, you'll start to see all the applications to math (especially discrete math). I've heard Structure and Interpretation of Computer Programs is a good book, and I plan to read it next semester, so maybe that's a good one for you. It uses Scheme (a Lisp) as the programming language, so the parallels with math are very clear.
As you said, it's dense. Enough so, that few people will read it cover to cover sequentially.
It's challenging, where "challenging" means that it requires living with some bewilderment and frustration while reading it. And anyone who is not as smart and knowledgeable as Knuth will probably experience both to some degree because what makes tAoCP great is that Knuth doesn't dumb anything down.
Over the years, I've found that tAoCP works well without having to dig deeper into the math [or MIX] than I am able or interested in diving...the abstractions are laid out well and understandable as abstractions without getting buried in algorithmic analysis...though the analysis can be interesting.
My take is that if someone is serious enough to try to tackle it, it will give back more than the effort put in regardless of the person's computer science background.
As a CS book, it teaches a lot of good CS concepts and techniques very thoroughly, and it analyzes the performance of algorithms very precisely. You'll not only use Big O notation, but you'll also figure out some of the constants. So, if your interest is in computer science proper, then this is a great introductory book.
On the other hand, if your goal is to be able to write programs, then definitely jump into using a language. Go find a book on a language and just start using the language to solve problems. After you get past the basics of programming, you'll start to see all the applications to math (especially discrete math). I've heard Structure and Interpretation of Computer Programs is a good book, and I plan to read it next semester, so maybe that's a good one for you. It uses Scheme (a Lisp) as the programming language, so the parallels with math are very clear.