I think someone on the BBS mentioned that Manifold was a fun origami puzzle challenge (thank you, whoever you are!). I ordered it on Amazon for $(removed) It's a pad of 100 square sheets of paper, printed with white and black squares on one side, and nothing (except folding guides) on the other side. The object is to fold each sheet so that all the white squares are on one side, and all the black ones are on the other. I just did two of them, and it was so much fun that I'm saving the rest for a long flight I have coming up.
Here's a PDF you can print out to try five puzzles.