What can I substitute for Mayonnaise in a traditional potato salad?
Direct substitution options would include sour cream, plain yogurt, or cottage cheese pureed in your blender to do a one-to-one substitution, but I don't know that these would necessarily solve your issue of having the salad sit out with ingredients that could spoil.  

This question has a whole list of substitutes.  Tofu is one that might suit your needs, although it would change the flavor profile.

Consider instead a German potato salad, which does not have mayonnaise to begin with.  Yes, this departs from your original recipe, but it will definitely solve your issue.