I learned Scheme in my intro to programming course and I loved it! It was very lean, simple and straightforward. No voodoo, everything is explainable, and an easy substitution-based "debugger" to step through your code.

On a side note, I don't think modern-day students will ever be exhilarated when they get "Hello World" to appear in command-line output. In the day of Pixar films, 3D games, etc the simple outputs are underwhelming. The exhilaration comes from making a program that solves a problem (real or artificial) and overcoming challenges along the way :)