I ask myself, "how would I teach my son to program?", and for all my copious academic and practical experience, "start with re-implementing car and cdr from lambda functions" isn't even remotely in the running. Sure, I'd introduce such things earlier than most people and SICP is still firmly in the running, but for that to be an introduction in the general case? Not so sure.
There's definitely an argument to be made that robotics is in many ways a much more realistic starting point. While some people may find the idea that we should actually start out by making a case to the students that their major is cool and important and gives them the ability to affect things in the real world vaguely repulsive, I'd say that it's an idea at least worth considering. The student that can leap from lambda, car, and cdr, to realizing that right in the introductory course is so exceptional that you're not going to hold them back anyhow.