I also remember playing with an old blue plastic Soma cube that my father had from when Soma cubes were all the rage. It came in a cardboard box with a little booklet of shapes to make out of it. At the time, I was more interested in just playing with it as a set of building blocks to make my own shapes rather than making the shapes in the book.
What really intrigued me was a version of the classic Patience Puzzle, shown on the right from Tucker Jones House's Tavern Puzzles site. I spent what seemed like an eternity working on this one, but eventually figured it out.
I think what I enjoyed about this puzzle was the fact that it operated under a series of clearly defined rules, and once you understood the rules, you could apply them to reach your goal. The first phase of solving the puzzle involved fiddling with it and eventually understanding what the rules were, and the second phase was applying those rules to transform it from the starting position to the solved position and back again.
At Middlebury College, I found out that a friend of mine, Paul Armstrong, knew an algorithm for solving the Rubik's cube, so I asked him to teach me how to do it. Thinking back, I regret not trying to solve it on my own, though at the time I just wanted to be able to do it. I practiced quite a bit and eventually could solve it in under 2 minutes...I think my best time was 1:30 or so.