I highly recommend teaching arithmetic in different bases and base conversion because it aids in the conceptual understanding of our ordinary base ten arithmetic and representations of numbers. If these students are going to become elementary school teachers, they're primarily going to be teaching kids how to add, subtract, multiply, and divide so it is really important for them to have a firm grasp on why these procedures actually work.

For a related "magic" trick, you can ask them why the telephone number trick works.

In general, a variety of discrete math topics including propositional logic and basic number theory would also seem suitable.