Back when I first saw it was in one of Bruce Dawson's courses where we did simple image manipulation. I think the task was to implement bitblit(move one rect of a bitmap into another rect on another bitmap).
I remember him grabbing one random student's assignment, throwing in some rudimentary timing and then saying, "lets see if we can do any better". By the end of ~15 minutes he'd sped the thing up 800x with a combination of reading by row rather than column, aligned reads and some other tricks that looked like black magic at the time. Looking back now it all seems fairly obvious once you know how the hardware works.
Good times.
Rich Hickey started clarifying it for me a little though. I can't dig up the interview he did, but he talked about classes being mini-DSLs and hindering reuse. That makes sense to me.
I much prefer generic functions and multi-dispatch in Common Lisp's CLOS and the new language Stanza - it just seems more flexible.
But generally, I want to think about data transformations and not little "machines" (objects) doing things things to their state internally.
At the end of the day most programs can be thought of as state machines in some way. But it's often hard to split them into smaller state machines. The thing is, state is hard to compose if it's encapsulated :-)