Put the balloon in the egg, and fill the balloon with hydrogen or helium. Depending on the weight of the egg and the density of the balloon, that may be enough to soften the landing. You can usually pick these up at party stores.
You could also do a parachute with weighed prongs on the bottom, and cushions between the egg and the prongs. Think of a lunar lander with a parachute.
If you're good with balsa, you could also make a Leonardo Da Vinci-esque glider.
You could also do a small helicopter mechanism, easily acquired at a hobby shop. You just need an RC speed controller and a carrying cage.
My favorite, however, is the spring-loaded ball. What you need to do is make two metal dodecahedron cages, one considerably smaller than the other. At every joint, you put a small spring with cushioning at both ends. However, this requires some metalwork skill. You could do it out of wood, but wood tends to snap on impact.