This is a good question. Here's my opinion.
1. Learn bash. The CLI is THE tool to use in *nix. Also learn something about bash scripting. A pretty good rule would be to never do anything in GUI that you haven't learned how to do in a console first. I recommend LinuxCommand.org
as a good beginner's tutorial.
(You seem to have already figured this one out.)
2. Learn the file structure. You have to know where everything is and what it does. What do all the config files in /etc do, for example? Where do you look when you're having a problem with X? What can you tweak and what should you leave alone?
3. Learn file permissions. These can be a bit complicated. Heck, I've been at this for 4 years now and I still don't know enough. But you should know how to change permissions on files and directories, and what will happen when you do.
4. Learn how to use a console text editor. Vi/Vim would probably be best, but at the very least, you should know how to edit the config file when X refuses to run.
5. Learn how to compile programs from scratch. The package systems are great, but occasionally you'll find you want to install something that doesn't come in a nice .rpm or .deb. Most of the time compiling from source isn't difficult, but when you do have problems, they tend to be hair-pullingly frustrating (I'm currently suffering through one of these now). Learn what to do.
6. Ditch the newbie-friendly distro. Ok, maybe not the first thing you should do, but something you shouldn't hold off on for long. "Easy" distros are nice for getting your feet wet, but they hold your hand too much. Get something like Debian, Gentoo, or Slack instead. When I first started out I went with Mandrake, which I had heard was one of the easiest for beginners to work with. But when, after a year, I still didn't really know what I was doing, I switched over to Debian and I was suddenly really learning
Linux. There's nothing like being forced to deal with a problem yourself to really teach you what's what.
(Yet another one you seem to have already figured out. But I put this one up for anyone else who might read this in the future.)
Of course, there's an endless stream of stuff to learn, but I think these six will put anyone on the fast track to competency.