Yeah, ANSI C might be a good choice. C++ though, is kinda only half object-oriented. It probably isn't a good first choice, although I managed to get through it as a first language. Java doesn't teach you memory management, but it does teach OOP, and it teaches it very well. OOP is what people want nowadays. Also, without learning pointers and memory management until he has some other programming experience under his belt, and perhaps learning C in a programming CLASS, rather than from a book, he is less likely to learn poor programming habits that will take a long time to un-learn.
Straight C is limited enough that it will teach you a lot about computers, while Java is strict enough that it will teach you some good habits. Whichever one you decide to start with, once you know it well, learn the other one.
Perl is great for whipping up quick little scripts, and if you spend some time writing it well, it is plenty readable. However, all the little ways it has in it for you to be lazy and save a few seconds of time when writing a script come back to haunt you when you try to figure out what that script does six months down the line. It is a good fifth or sixth language, though, and everyone really should learn it, especially if you are interested in system administration or web stuff.
EDIT: Some hints no matter what language you choose:
1. Use meaningful variable names. A few more keystrokes now when naming your variable takes a lot less time than scrolling around trying to find what you are using "n" for.
2. COMMENT YOUR CODE! Any time you do something particularly complex, separate out that block of code with a bit of white space, and put a comment explaining what you are doing, and how you are doing it. At the very least, document what each function does, and toss in a short comment telling what all of your loops are doing. If you think a particular bit of code is a messy way of doing something, say so. You will thank me when you go back to your code in six months and can still understand what you were thinking.
3. Break your program up into functions. If you have some bit of code you end up pasting in two or three times, it should be a separate function. If you have a function that takes up two or three screens, try to break it up into two or three functions (as long as that makes sense to do). Sure, function calls take a bit of time, and make your program (slightly) less efficient, but most compilers will optimise that out, and when you are first learning to program, that really isn't the time to be THAT worried about efficiency. Algorithm complexity, sure, but not the tiny amount of time lost on a function call.