Lambda the Ultimate had two interesting posts recently related to teaching introductory programming. This interests me because, in the spring quarter, I'll be going into my 6th edition of our second quarter of intro programming, (Jeez, has it been that long). I've never been really happy with the course, partially because it winds up being overconstrained by the courses directly in front of and behind it. Be that as it may I'm always interested in how others approach such courses.
Peter van Roy, posted a bit about his experience introducing programming semantics early in the student's careers. Due to the formal rigor involved this would seem to work at schools with heavier mathematical pre-reqs in their CS programs, which I think is typical of European schools. Good discussion ensues in the comments.
Similarly, a post by Chung-chieh Shen ignites some interesting commentary on the utility of Structure an d Interpretation of Computer Programming, MIT's ur-book on programming. That was my introduction to rigorous thinking about programming and is the textbook we use here in our first course. Bonus, a link to Joseph Bergin, who seems to have done quite a bit of thinking about CS pedagogy.