My favorite aspect of teaching cryptography is the interdisciplinary nature of the subject. The most successful students use mathematical, language arts, and computer skills in tandem. Other areas that overlap with the subject are engineering, ethics, history, and politics. The course requires that students are able to communicate technical ideas in both written and oral form.
I teach the course by taking two journeys concurrently. One is a journey from classical cryptography through mini-examples of modern day methods. The other is mathematical that includes modular arithmetic, group theory, matrix operations, and elliptic curves. I usually alternate the lessons on cryptographic theory with those on mathematical theory so that students don't get burnt out by either.
I have never taught the course the same way twice. This has been, in part, because the access I have to a computer lab has been variable. There are some very good free tools available such as CrypTool and CoCalc. Students can used the cloud based CrypTool to test out theories, experiment with various protocols, and do analysis on a piece of ciphertext efficiently. It is slightly anachronistic to use 21st century technology to crack 19th century codes, but it is easy to get worn out doing the pencel-and-paper method. Much like calculator use, there is an appropriate time to introduce computation into the course.
Since cryptography is such a multidisciplinary subject, it appeals to a great number of students. For those of us that played spy as youngsters, we are a little bit nostalgic for the days of lemon juice, rail ciphers, and outwitting the "enemy", in the backyard. Living in a post-9/11 world brings us back to the present. I believe that the relevance of cryptography in our daily lives is another reason for the appeal of the course. The security of a cryptographic system and the fate of nations has gone hand-in-hand throughout history. The crossover of so many different disciplines makes the coures easy for me to adjust depending on student's interest. It's a joy to teach the course.