As someone eyeing SICP with previous programming experience should I do SICP first and then do these koans? How big is the difference between Scheme and Common Lisp?
You dont do SICP to "learn Lisp", you do SICP to learn fundamental programming principles. SICP just happens to use Scheme because one of the authors of SICP was also one of the authors of Scheme. The difference between Scheme and Lisp is big enough to justify them having different names and Scheme not being "just another dialect of Lisp".
The problem with Scheme is not the language, the problem is that the ecosystem is so hopelessly balkanized, that it is useless for practical purposes and nobody uses it for anything interesting except for teaching of SICP. You have tiny standards covering only base language constructs, and everything else is left to implementations of which 1001 different one exists and each implements the same stuff in a different, incompatible way, so there is no code portability. So an large number of Scheme users, instead of developing interesting and useful _new_ libraries, instead rewrite 1001 different implementations and 1001 different manuals covering the same area. If you write something and tell me you wrote it in Scheme, the first thing I'd have to ask is "Which one?" because your code will not run on the 1000 remaining ones. The scheme ecosystem is the prime example of code non-reuse, of the NIH syndrome and waste of man-decades of effort, so while the language itself is nice for teaching, the existing worst-practices are examples of what _not_ to do.
SICP doesn't 'just happen' to use Scheme; the simple language from a well-chosen combination of powerful mechanisms is the kind of thing they're teaching you to design. The medium is part of the message. (Yes, you can solve the problems using another language; I used XLisp.)
On 'dialects of Lisp': it used to be standard for very different Lisp-family languages to be called that, while nowadays someone will always contradict you if you do. It seems more of a social change than a technical one to me. (I first noticed it among Common Lispers after the AI winter.)
I know someone impressive doing real work with Scheme (though I recommended they try Lua). I don't know whether you're right about the Scheme ecosystem, as I've been elsewhere the last 15 years.
I would go with "How to design programs" - looks at the beginning to be siplistic, but it gives a lot of understanding about lisp like languages.
Then I would go with SCIP and then Koans.
I am treating lisps as a kind of mind game (I dont like crosswords :) so I do Lisp) since I cannot use it for everyday job so from my point of view Scheme and Lisp are not very different. There is different approach to things like mutable state and other more advanced concepts, but basics are the same.
If you want to have at least an illusion of learning Lisp that can catch up one day, learn Clojure. Or go with Scheme's ugly duckling son - JavaScript. :)
SICP [2nd edition] is flat out just a more readable book than HtDP [first print edition, second edition is not in print but looks to be significantly improved].
As textbooks, it may be a bit of a different story, the tone of SICP is certainly cockier. There's less acknowledgement that mathematics is just domain knowledge within the context of an introductory "computer science" course. Then again, HtDP had two decades of experience with SICP upon which to draw. It also has the practical advantage of assuming that students had high levels of access to computers capable of running Lisp. That wasn't the case in the late 1970's and early 80's (or even the late 80's and mid 90's).
A course (lightly)based on HtDP is also starting in Coursera in a few days- https://www.coursera.org/course/programdesign. It uses Racket and the first two weeks of videos are already up so you can preview them.
While CL and scheme are both lisp dialects, they are quite different. Just to make a pair of examples, CL has two separate namespaces for variables and functions, scheme only one; scheme has guaranteed tail call optimization (which is used often to solve problems recursively), CL depends on implementations. To do these koans I would first go through Practical Common Lisp by Seibel http://www.gigamonkeys.com/book/
The optimization of tail-call optimization is converting some recursive procedure descriptions into iterative processes. A recursive procedure description may instead describe a necessarily recursive process. The difference between descriptions and the procedures they produce is one of the issues covered in SICP - most explicitly by Ableson in one of the videos.
If you're already a programmer, you should probably read Paul Graham's On Lisp. It's a technical book, written by an advocate but before he became a VC or took up writing on woolly topics like the relationship of programming to painting.
The problem with Scheme is not the language, the problem is that the ecosystem is so hopelessly balkanized, that it is useless for practical purposes and nobody uses it for anything interesting except for teaching of SICP. You have tiny standards covering only base language constructs, and everything else is left to implementations of which 1001 different one exists and each implements the same stuff in a different, incompatible way, so there is no code portability. So an large number of Scheme users, instead of developing interesting and useful _new_ libraries, instead rewrite 1001 different implementations and 1001 different manuals covering the same area. If you write something and tell me you wrote it in Scheme, the first thing I'd have to ask is "Which one?" because your code will not run on the 1000 remaining ones. The scheme ecosystem is the prime example of code non-reuse, of the NIH syndrome and waste of man-decades of effort, so while the language itself is nice for teaching, the existing worst-practices are examples of what _not_ to do.