You've received some excellent responses here, but I wanted to tell you about about my own efforts in this area.

I'm in the Department of Romance Philology at my University and the one thing that has gotten the linguists in our department all excited is the power of regular expressions. Regexen are central to a lot of what so many Perl programmers do with the language. As a matter of fact, Perl's regular expression support is so well-developed that many other languages and tools use "Perl compatible" regular expression engines. Regular expressions are even useful for non-programmers and lead logically into simple substitution scripts for your next step in converting your flock.

One such program that is used often in linguistics and literature departments is Monoconc (a concordancer). Even word processors like OpenOffice Writer or Microsoft Word support regular expressions in one form or another.

The advantage to this approach for you is that you teach them something that is immediately useful on a practical level, but which has a solid theoretical foundation, all without sacrificing necessary detail by taking a too broad approach towards introducing them to Perl.