I've taught an intro course to UNIX and systems administration to MIS students years ago. The concepts are the same for Linux. And I've got a pretty good background in instructional design. If your students are starting off, teaching them complex sed/awk stuff, packages, pipes, and the GUI is going to start already leaving them behind. And there are so many people who work on that stuff, but don't understand the basics.
In the course I taught, I started with things that many of them, even the Linux users among them, never knew about their systems. Such as the fundamental that *everything* in UNIX/Linux is a file. Directories are really files. The keyboard is a file. So is the display. And the network card. That is an important concept to understand later why redirection, pipes and the like work as well as they do.
I also taught things like symbolic vs. hard links. And how that all relates to inodes. Therefore, how you can move or copy files and create symbolic links that can change the one or the other. True of just about every file system.
Then you can get into how processes work. And how all of them spawn from one root process (initd). Children, zombies and the rest come into play, and the kill command, and how to use a tool like top to see how they all work. And how to reset them when they run amok. I used Mark Sobell's book on UNIX, but he has newer ones out on Ubuntu and Linux and such as well.
You can then continue with a basic editor like vi, which is a good one simply because it's likely going to be on just about any system they'll come across. Emacs is not as ubiquitous, so I won't get into a war over which is better. If you like emacs, you can install that too, but some systems won't have it and you may need basic vi or even ed skills to get the box going enough to get emacs installed. The same is true for shell programming. I would use bash, simply because the context and syntax carries across most systems well, regardless of the type (Linux, BSD, Mac OS X).
Once they get all that you can get them into pipes and redirects and how they can be used to create wonderful things by coupling lots of simple tools together.
And all of that even without a GUI!