I've had a neat puzzle bookmarked for a while: the Naef Cubicus. It's a set of shapes that fit together in many interesting ways and form a full cube of 64 blocks when packed together correctly. What caught my eye was the diversity of shapes it could be assembled into, but the downside was the cost: paying $100-$300 for some blocks isn't really my thing, even if solving puzzles is.
What's great about this project is that the little cubes are just square cutouts on thick plywood, so they can be made even from the smallest of scraps. For mine I used 1/4" thick plywood so I cut out 1/4" x 1/4" squares, thus making cubes with 1/4" sides (roughly; kerf wasn't too big of a deal). That made dark and light faces (light from the wood, dark from cut edges) that I could rotate and make interesting patterns while gluing the pieces together.