That said, I still think the best single "textbook" on computer science is the Cartoon Guide to Computer Science, however it looks like this "unplugged" book is much more practical for showing ideas to a group or as inspiration for other approaches. Think: Royal Institution Christmas Lectures, or "Think of a Number", rather than "traditional lecture".
Interestingly I came across that site via LULU (the unplugged book is here)- a publishing site which was apparently founded by Bob Young (one of the founders of Redhat). Incidentally lulu also appears to have 3 books on ubuntu that looks quite nice - on desktops, servers and one on packaging. I don't know what they're like, but given their aggregate cost is about the same as 3 beers in london, that's pretty good going!