I'm a teaching assistant for an intro to programming class, and I do feel that solving an endless train of toy problems is problematic for students. From my experience, the best way to learn is to understand a real problem, determine it's requirements, then design a solution. However the professor and I struggle to find real problems that are approachable for novices with varied backgrounds.
I saw an open source class called nand to tetris where students had a semester to create a machine that could play tetris, starting with only nand gates. I thought that seemed like a much more fun progression for computer hardware than the undergrad courses I took. I would love to discover something similar for programming but so far I haven't found it.