Perl is as good a place to start as any. If you look around, you will notice that there were two languages that were invented strictly for teaching (BASIC and Pascal) and both have had remarkable runs as real working languages over the years. Even now you see the newest BASIC (VB 6) up against the newest Pascal (Delphi 5).

The grim fact is that your first language seriously colors your later choices and mental parsing. So much so that many people are still more comfortable in a majorly bastardized version of their first language than one designed to address the needs of the task they are assigned.

If you know what type of task you will be performing I recommend you pick as a first language the one you will do most of your work in. If it has been years since you programmed, I tell people that Perl is to Basic what Java is to Pascal. Nothing LIKE it yet strangely familiar.

As to the original post's question, teach them more than one language at once. I recommend a language like Perl or old BASIC with inflected verbs and nouns (&subs vs sub() and $var vs @var vs $var3); a stricter language like Java or Python with a plainer grammar; and a radical grammar language like Scheme or Forth that makes you look at the logic of the program from a whole different angle.

There are a lot of good languages out there, make sure you give them a taste of more than one and let them find the once that fits them like an old shoe. Personally I wouldn't be half the Perl programmer I am without Lisp, x86 ASM, Forth, Basic, Pascal, C and more all floating around in there. (Lisp really helped with Perl, one week after first playing with hash arrays I yelled out, "Oh! Dot lists!" =)

--
$you = new YOU;
honk() if $you->love(perl)