I would say that it all depends as to where you want your career to go. If, for example, you want to be web oriented, go for perl and Java. I'd add PHP into the mix as well. You'll also learn a lot about web servers along the way, which isn't a bad thing.
In general though, my advice would be to start off with perl. If you can create shell scripts the you're half way there with perl. The syntax can look a little crazy at times, but you soon get over that. To start off, get the "Learning Perl" book from O'Reilly, and then move on to the "Programming Perl" book.
Next move onto C. Unix is written in C, so you can't go far wrong with it. If you don't have a C compiler on your Unix box, go and get Linux installed on your home PC and user egcs. Then get a decent C tutorial and get hacking! I found that getting hold of source code for open source packages and digging around taught me a lot.
As far as C++ goes, I've never had to touch it, so I can't really say "do or don't". I've always found perl, C, or a combination of both to be more than enough for any task.
On the experience front, once you've gotten a grasp on perl or C, how about writing your own package that fills your own personal "I wish I had a program to do..." hole? Then release it over the 'net, announce it on Freshmeat, and keep it maintained. In you next interview the conversation ma be... "I wrote abc package that does such and such and has been downloaded xyz times from the 'net. It's at version 2 at the moment, and here's a copy if you want to take a look at it." Plus, you would learn a heck of a lot more actually doing something with the knowledge.
Anyway, enough of my ramblings. I hope there's been something of help in there.
