My 2-cents:
What language should I start with?
Perl, or actually, Python. In my experience they are the easiest to setup, pickup, and get moving in, while the underlying implementation of programming languages is abstracted away.
What are essential computer science
topics that I should cover before
jumping them into computer
programming?
Before actually programming? I would go into basic programming constructs such as different variable types (or in the case of python and perl, different types of data), such as integers, floating point numbers, and strings, to start off with. Then move into control and flow constructs such as if-then-else statements and loops. These are essential to almost all modern programming languages. Then move into data structures later, although mention lists and arrays, since in python that's what you'll be using most.
What readings can I incorporate to
make the topic interesting and
non-overwhelming? If we want to spend
a year on it, what topics should take
priority and must be covered in 12
months?
After introducing them to a few languages and writing small programs in them (Hello World, adding numbers, manipulating strings, opening, reading, and writing files) have them choose a language they like best, and have them build something they like with it. Get them a book or provide online resource they can turn to for help.
Again, these are non computer science
folks, and I want to keep the learning
as much fun as possible.
Bring in as much (fun) reality as possible. Learning hashes (dictionaries)? Bring in basic cryptology. Learning trees? Bring in Facebook and friend networks. Learning algorithms? Write a program that guides the user to making a pizza (an algorithm is simply a recipe). Visualize data structures like trees whenever possible.
Once your friends are comfortable programming in a language of their choice, you have to let the "fun" part go a little bit in order to get into higher-level concepts. Programming is a lot of fun, but it isn't all fun, there are frustrations that can come up, just like in anything else you might learn.