Just an idea here, but it sounded good in my head ;)
How about design puzzles where you start with a small known protein that is useful or interesting.
Once it is loaded allow design as normal, however:
Limit swapping amino acids to changes from the same group and grant a small bonus for deviation from the original sequence.
Yes. I like the idea. We could design mini-antibodies to new ligands/antigens. We could re-design known clefts to bind transition-state analogs in hopes of getting new enzymes (I hope that idea isn't too 1980's- 19990's). We could work on stuff that binds to environmental toxins for bio-remediation. Lot of potential I think.
This reminds me somewhat of puzzle 1059.
You are given a set design and asked to improve it. You can change the shape of the design up to a set limit but over that limit you are penalized. You can change amino acids but I would think you are somewhat limited by the shape of the design.