Well, many have already been mentioned that I know about...but
If you go to my web site www2.austin.cc.tx.us/pauler you can see a page of links that lists a lot of Photoshop tutorial sites. On this site I also list 5 of the main projects we teach in Digital Imaging classes. I have lots of little exercises I use in class but haven't posted them. By the way "Adobe" offers lots of help plus they do have a special 'educators area" with tips from teachers by teachers.
I have another web site for art educators but it was started and never finished. Some of the lists are activities that might be adapted to Photoshop. Even the ClarisWorks/Appleworks ones! You might want to see what I started at http://pauler.home.texas.net/
Books like WOW, and Tips and Tricks are ok for ideas and lots of "glitzy" lessons. For the fundamentals you might consider the classroom in a book (tutorial based). The Quick Start guides are pretty good reference, And Easy Photoshop by Que (not pretty but cheap with simple step by steps.) might be worth looking at. Also I use Ben Wilmore's Studio Secrets book. It may be more thorough and advanced than desirable but it is also a good book about "digital imaging" not just Photoshop.
Barnes and Noble has had free online Photoshop classes. Might be worth a look. (Has someone mentioned that?) There are references there for more if interested.