My first suggestion would be lisp. It's a very nice language, similar enough to Perl that if you like one you may like the other, but different enough from Perl to stretch the way you think about programming just a little. Lisp, like Perl, is a general-purpose programming language.

Another possibility is Inform. Inform is not a general-purpose language, but is targeted toward a fairly narrow (but very interesting) problem domain. It's Turing equivalent, of course, and quite flexible, but really geared toward a specific type of program. The advantages of Inform are twofold. First, it will teach you to really appreciate the object-oriented paradigm, because the object model in Inform is pretty advanced (WAY beyond the Perl5 one), and a *very* good fit for the intended problem domain. Second, Inform has a really excellent book, the Designer's Manual, which is without qualification the best computer-related book I have ever seen. (It's also available online (free of charge), as well as in print.) Inform will change the way you think about object-oriented programming, guaranteed. Oh, and the intended problem domain is one that immediately captures the imagination, so it's fun to program in.