What are food additives that help popsicle/shaved ice melt slower? What are food additives that help popsicle/shaved ice melt slower? 

Simple popsicle ingredients: water, sugar, flavoring 

I used agar agar and gelatin before, but don’t want to: The texture is not the same, it feels like icy flakes, not like fluffy snow.
You could experiment with decreasing the sugar...higher sugar means quicker melting.  However, if you want to eliminate all melting, you could try making a fluid gel using low acyl gellan (typically 0.5% to 1.25%...so, it doesn't take much). Then freeze that. It is more freeze/thaw stable than agar.