I see. You have two use cases going on here:
- Temporary storage of intermediate files so that you can sort through them all to use individualized clips of each recipient.
- A final export format and storage media to be distributed to the recipients
For the first use case, your goal would be to maximize quality, maintain edit friendliness and be able to fit all the files on the storage device you have available on your editing machine. For this, I could recommend intra-coded H.264. Just do some math to figure out what the highest bitrate you can use without filling up your hard drive. For 720p, I bet you could go as low as 50Mbps and keep perceptibly perfect intermediate files.
For the second use case, I would highly discourage any optical media. Your grandchildren will probably never own optical drives. I would encourage you to look at USB flash drive gift sets:
For encoding, you would want a format that will be compatible with as many devices as possible. I would suggest MP4 file with H.264 60 frame GOP at 8Mbps. If you use the x264 encoder in 2 pass mode, the quality of 720p at 8Mbps will be astounding and it will play on any device for the foreseeable future.