Structure for an introductory course on cryptography?
I recently read Understanding Cryptography: A Textbook For Students And Practitioners by Christof Paar &amp; Jan Pelzl. I can say without a doubt that it addresses all your bullets and in the meantime it's easy and fun to read. 

I have an MSc in Information Security so everything I read I already knew but some of the concepts were so well put that I felt I got a better grasp on how some things work. 

As I was a reading it I thought to myself that if I ever teach a introductory course in Cryptography I'll follow this book. You can give it a shot, see if its format suits your needs as a roadmap.