If I was teaching a total newbie how to program, I would probably start with a totally simple, procedural language like BASIC (e.g. QuickBasic, Real Basic). Maybe in today's day and age Python would be a reasonable equivalent, or C (as long as we kept it simple). Make sure they learned and were totally comfortable with variables, functions, OS calls, file systems, math, string manipulation. Then progress to more advanced stuff, bringing in object oriented programming paradigms, pointers, stuff like that. Still all console based.
Once the learner was totally, completely comfortable with programming in the console world, including proper design and architecture of simple data structures (like working with arrays, linked lists) and some simple design patterns (dealing with inheritance, event models, publisher/subscriber, exception handling), then we'd look at GUI stuff.
I imagine Java would be pretty easy to work with in terms of GUI stuff. But then, I program in X/Motif (C++) for a living now, and I get the feeling anything would be easier than that! (The advantage is that any problems I have are generally a Google Groups search away. Of course, most of those threads date back to the mid 90's...!)
As for books, whenever I need a book on a subject I generally try to get something published by O'Reilly. In my experience that practically guarantees a winner.