References on teaching introductory programming courses
Here's a survey paper and there are others.

You might want to consider the inverted method also known as outside-in, which differs from the traditional bottom-up approach.

This article on the application of problem-based learning to first year programming reports some successful results, mainly in terms of secondary skills learned by students. The cost is a major investment and restructuring by those involved.