Puzzle box of the month. Each month everyone gets the same puzzle. You do it together, apart. Brilliant, because the puzzle comes with pamphlet showing picture and info, but box is the same as shipping box. Optionally include envelope for storage (nah, let them use their own envelopes!).
There is a special paper material that doesn’t tear. It is proprietary, which sucks, but there is probably quite durable paper that can be printed on, with the image of the puzzle contained within.
I’m thinking envelope-in-an-envelope for shipping, and easy storage.
As a subscription service you could have numbers for a given month to do bulk print orders, and potentially the print facility could handle bulk shipping-labeling.