I would suggest to start with either C or Pascal as they are both quite strict, basic and yet powerful. After that you can move on to the OO orientated version of either of it. (C++ / Delphi Language(Object Pascal) and learn the concepts.
That's because if you just start explaining what the declaration is, you're going to lose people when you start using strange words like classes and all these things that they have no idea what they are. Then you try to explain those and you just end up getting ahead of yourself. The idea is to ignore those for the time being and when you start getting some background on it, you can then discuss the parts that've been lying around for awhile.
Well, if somebody wants to learn to program oneself, he or she should be able to get through that...
PHP is really easy to learn and even easier if you already know an other language. The syntax is similar to that of C(++).
As for the pointers: Java does support "pointers", but in a different way than C. You can have a reference to an object, but you cannot manipulate it. Meaning: you cannot manipulate the address(a pointer is basically a variable that contains an address) itself as you can in C and other languages. This is has advantages and disadvantages as well: for one thing: security is increased but also you are often forced to use less elegant ways to solve problems, error rate is also decreased. I for one like pointers a lot
If you really want to get a deep understanding of how it(programs) actually "works", I recommend you to go through the basics of Assembly, but don't do that too soon

It really improved my understanding of programs and I now see my code quite differently than I did before, also get to know how to optimize your code better if you know what the compiler does with your code.