Being a professional software developer who works in Java, and a former nightclass teacher of Java I can say without reservation that Java is NOT the best first language. Java forces you to use Object constructs from the get go. These things get in the way of communicating the principles that you want to teach.
My first "Introduction to Programming" course was given through Java and it transpired exactly as Hairy1 describes. We got tied up in knots with objects, constructors and parameters and a simple task of multiplying two integers took two weeks to teach because the lecturer wrapped the whole thing up in a pile of "class Rectangle" bullshit.
By contrast, at the same time, we were being introduced to assembly on a Motorola 68032, and one of the grad students had put together a simple wrapper program to let us write values to registers using simple pseudocode-like commands. I learned more about programming and problem-solving from THAT course than I ever did from the Java one.
More recently, a friend of mine taught a beginners' course for an evening CS course in the same college (Trinity College Dublin) and when he was casting around for a simple language that wouldn't get in the way of teaching basic programming principles but could still be used to create something more satisfying than command-line output, you know what he ended up going for? PHP. And apparently they loved it.
You can't start with objects; it's too abstract for a beginner. When you've done variable assignment, operator precedence, control structures, simple functions, scope, loops and arrays, THEN maybe think about introducing classes.