First Consideration: Usefulness
In terms of usefulness, I consider Python to be the best choice. It is capable as a web language, a shell scripting language, and also for developing serious GUI applications. It also has very wide cross-platform support, a large community of developers online, and is a live language which is still being actively maintained in both a 2.x and 3.x branch.
Second Consideration: Syntax
I favor the syntax of PHP because it is very close to C syntax, and most modern languages are based upon C syntax in one way or another. This would imply that I also favor the syntax of C, and I suppose that is true. I am bothered that PHP requires an opening php tag at the top of each source file, and this is evidence that I am trying to use the language for something for which it was never designed. I believe there is too high of a barrier to using C for keyboard input and console output (a common task for beginning programmers) mainly because of its poor string handling, and because of this I went looking for other options more serious than PHP. Something about Python's syntax grates against my nerves, and I can't quite figure out what it is. (For the record, I don't mind the use of white-space to define blocks, which is unique to Python. I think it is pretty & clever. The only downside I see is potential trouble sharing code online because sometimes when code is copied and pasted via email, blog, or forum, it tends to get mangled and all the lines become left-aligned in the process.)
Third Consideration: Science?
I think either C or C++ would be a good first language because I believe there is value in learning a statically typed language so that the manner in which the computer stores values in memory can be better understood. This may be an antiquated idea to worry about, however, since in practice it may not be necessary to worry about such things any more. Also, I believe the philosophical concept of data types can be acquired just as easily by learning a database system such as MySQL.
Conclusions?
I'm unhappy with the options, but I have decided it would be reasonable to try to teach both PHP and Ruby. I have started with PHP because it is the language I am most intimately acquainted with, although I see Ruby as the more elegant language of the two.
I wish they were not both so scripty and dynamic. I like those properties in a language I'm going to use on a daily basis, but I think there is value in learning something more strict as well.
I wish there were more options available that also fall into the "useful" category.