A lot of my favorite programs in middle and high school were written in QBASIC.
That's because you could write stuff like
SCREEN 12: CLS
PSET (8, 3), 10
CIRCLE (100, 200), 45
LINE (15, 15)-(25, 25)
Drawing stuff is really a lot more interesting than boring text manipulations or algorithms -- especially for a beginner of middle/high school age. Programming is fun because you're creating your own world with its own rules -- and that resonates right away with a student when that world is something they can visualize and interact with using realtime graphics, rather than just read about with text output.
Python/Pygame is probably the closest modern equivalent. Especially if you put some of the boilerplate like window creation in a file, and tell them to copy it into their program's directory and import it. (Or, having them run the boilerplate file, and having that file import the student's code, might work better.)
Show minimal drawing stuff right away. Then you can go in a lot of directions. Use a FOR loop to draw a pixel or circle going from left to right across the screen at a speed of one pixel per frame. Then you want it to reverse direction at the right edge, so you can show IF statements. Show how you can simplify the code by using negative numbers, this will introduce the concept of having velocity. Having a circle reverse direction is a little trickier than a pixel, because you have to take into account its radius.
Then make your objects go at 45 degrees to the coordinate axes -- more on the velocity concept without being too difficult/technical. Or have an arbitrary number of them -- now you have arrays. Or teach them how to replace circles with an image downloaded from the Web. Then put a background on it. Then introduce user input into the equation. Maybe you can click the mouse to spawn a new particle or move the particle to the mouse location. What happens if it's a circle, you did the radius fix, and the user moves it closer to the edge than it would naturally get? Then think about gravity: Just have the velocity increase a little in the "down" direction every frame. Of course, if you're imagining the bottom of the screen as a wall, then you have to figure out how to stop it when it tries to fall past the bottom of the screen.
A little more work, and you have a simple platform game. You just have to come up with an input scheme, figure out how to do vertical walls, and how to make the "bottom" be different heights depending on the x coordinate. Then have enemies that can "collide" with the player.
For a class project, every student (or small group) picks a different feature to add to the engine -- moving enemies, scrolling, healthbar, dangerous terrain, levels defined by files, levels generated randomly, enemies that shoot, players that shoot, (you could have them "toss baseballs" or "cast spells" if "shooting" is too violent), an animated player sprite (a great idea if there's an artistically talented student in the class, though even the most lacking artists could still complete the assignment with a quick visit to opengameart.org), or student ideas (must be approved by teacher). The teacher picks a couple features of his own to implement. Then everyone gives their patches to the teacher (for grading). After the patched versions are submitted, the teacher publishes them as diff -u style patches to the entire class, and everyone now has to add as many features as possible. This teaches the students a little bit about how collaborative development works in practice.
Having a high school devoted to CS lets you do a really good job with this concept, because you can devote an entire course to it. This should be their first CS course. Its primary purpose is inspiring them, motivating them, getting them excited for the possibilities of what they're learning. It will also:
Introduce students to different program constructs.
Introduce some physics/mathematics theory for the particular problem domain.
Introduce students to the way mathematical modeling/theory can be applied to a practical programming problem.
Introduce students to the use of external tools, libraries, assets, their OS's command-line interface, and API docs.
The beauty of having a high school devoted to CS is that you can have an intro-level project-based course that doesn't have to be comprehensive in any of these areas; later courses can do that. If you don't need recursion or string manipulation, you don't have to cover it. If you don't cover every available tool or every corner of your API docs in this course, that's fine. If this course is in Python because it's the best language for the purpose, but the AP exam is in Java, that's perfectly okay -- they can pick up Java in another class. The goal at this point should be to teach them how, not what -- that is, focus on how to program, and only cover what tools are available on an as-needed basis.
Having current or past large-scale projects when you're programming is useful because it alters your perceptions. Your brain recognizes when the thing you're learning is applicable to the project. This connection helps the memory become more permanent -- the brain flags it as "important" since it's related to something it spent a lot of effort on in the past. The connection also helps the memory become more integrated -- there's now a "pattern match" between the concept and its real-world application, so it's easier to both remember the application when you're confronted with the concept, and remember the concept when you're confronted with the application. You may not cover the entire AP CS content, but what you do cover, you can be sure your students will remember when they take the AP exam 3+ years later.