Strictly talking about the difficulty of concepts, a curriculum based off of SICP (or something with a similar emphasis on functional programming or math) will probably be full of new concepts even for those who've had some experience programming. I'd say this is a good thing for everyone involved, because it both levels the playing field for those without experience, and ensures that those who have some still get something out of the course.
Most schools, though, start with imperative concepts (as does AP Comp Sci), which isn't a bad thing either, but someone with experience won't get as much out of it until later in the course.
If you're applying to schools or about to start a class, it wouldn't be a bad idea to dig through the department website and see if you can find the site for the class to see what it entails.
* What is your background? Have you been exposed to mathematical proofs, logic, discrete math, or computer programming?
* What is your purpose? Are you worried about filling a single freshman requirement, or are you planning on studying computer science?