we haven't done this yet, but plan to. make sugar cookies. toddlers will require lots of help, obviously. my daughter likes to roll the dough and cut out the shapes. after baking, we ice them and let her shake sprinkles on to them. admittedly, this is a messy one, but still fun. so i guess it didn't meet your non-messy criterion.
another one we did was coloring wooden pre-made ornaments. i got a few at joann's fabrics for like 40 cents each. we already had markers, so she just scribbled on them. i got ones that can hold a photo, so one of these days i'm going to print a photo of her and give it to grama, aunts, etc.