Just make sure that when your done teaching them, they have something that they can use and show off.

IMHO, a very wise advice!

Database stuff like CD-Collection, Address-Collection, etc. pp. is quiet boring, but maybe I was exposed to too many beginners books for different languages.

If you want to do a real interesting project teach them something they can't do with software bought from the shelf.
Teach them magic.
E.g. Showing them how they as consumers can master the WWW with the help of libwww or WWW:Search could be the killer application for beginners.
If you teach them that everbody can become a magican with the help of perl, they will love it.

Hanamaki