Introducing A* Search Algorithm
I usually teach Uniform Cost Search (UCS) before A*, since it is basicaly A* without the heuristic (and it reduces to BFS when all costs = 1, so it is pretty straightforward to explain). Then I teach A* and show them animated examples of the explored nodes in comparison to UCS (here you can find excellent interactive examples). 

In this step, one analogy I like to use is about mazes: Imagine yourself inside a maze from which you must find the exit, but you have no idea where it is. This is UCS. Now imagine there is no ceiling in the maze (like the Harry Potter one), and there is a tower in the exit which can be seen from anywhere in the maze. Now you can make more informed decisions in your search, biasing choices in that direction. This is A*.