I think of this as a two sided issue. One is teaching the ideas of programming, that is variables, loops, conditionals, functions, objects etc.
And the other is focusing on teaching a programming language proper.

As an aside, I still consider Logo to be the perfect marriage of the two, where you could either muck around with the "turtle", or actually create fun stuff while utilizing the tools of programming. But seeing as this is not cool enough for today's audience, I refer mostly to two tools:

One is "programming games". Not in the redcode sense, but stuff like Human Resource Machine which revolves around solving puzzle using said programming tools.

The other is JavaScript. It's ubiquitous, and you can get the results of your changes visible immediately, like the way we used BASIC in the olden days. In fact, nowadays every browser comes with a Javascript REPL of its own, and once the student gets more acquainted with the language, code examples are legion, and are handy, unlike the usual "I learned Ruby/Perl/Python, now what do I do with it (other than looking at projects that have 50,000 LoC and do crazy magic)?".