But an average student might need the exposure to other "common" paradigms from C, Python, or Java, before getting introduced to SICP, to "fully appreciate" the power of functional language.
Pedagogically speaking, I think this is backwards. SICP isn't a course in functional programming; it's a course in programming. And the use of Scheme is critical, because it doesn't waste time on nonsense like classes and structs and other ephemera -- you just jump right into the conversation with the computer.