I'll share a few things that I have done in the past to expose students to interesting AI topics without having them write working programs.
1.) To discuss expert systems and rules-based systems, have the students write out a list of rules (their best strategy) for playing tic-tac-toe (or another simple game that they should all be able to play well). After finishing their own set of rules, have them swap with a partner and attempt to lose, but still following the rules that were handed to them. This exercise has shown the difficulty in creating expert systems and exposes that we have so many assumptions that we don't realize.
2.) I really like Reinforcement Learning and created an activity where students are given a simple two-player game in which one student plays against the learning agent. The learning agent starts off choosing between actions with equal probability of selection. After a game is won or lost, the probabilities for actions taken that game or increased or decreased respectively. I implement this by using sets of colored tokens that can be removed or added to. For this activity to work, the game was be brief; the one I created never has more than 3 moves for the RL agent, it can only visit 14 possible states. I print out each of these states and tape the pictures to 14 different cups. The legal actions are color-coded with the colored tokens in the cups.
3.) Ant Colony Optimization is interesting and accessible. I'll show pictures from Marco Dorigo's experiments with actual ants and bridges. We'll discuss the concept of minimal spanning trees and some real world applications for them. The I'll end up using an online ant colony simulator.
If you want more detail about any of these, I'd be glad to share my experiences and more details.
If you're looking specifically for something they can program that exhibits intelligent behavior, you'll be extremely limited. One option might be an accessible robot kit (Mindstorms, etc) and have students work on obstacle avoidance, color detection, etc.