A prime staple for BBQs and picnics, potato salad can be both a person's crowning achievement or miserable downfall. First off, it's one of the prime causes of food poisoning at picnics because of people not keeping the Mayonnaise in it cold. I presume if you used a vegan egg-less mayo instead you could probably pull it off, as it's the eggs that likely go bad. Mayonnaise is mostly some sort of oil blended with some sort of vinegar, with an emulsifier in it to keep them mixed and cohesive. Eggs do this very well, but make the overall product heat sensitive, and typically have to have pasteurized eggs, because raw eggs (store bought at least) tend to be kinda dangerous uncooked. And you don't want to be the person who brought the bad potato salad to the picnic!
Otherwise, the hardest part is knowing what to put in it, what *not* to put in it, and boiling the potatoes just right. One of the tricks to achieve that is running cold water over them the second you dump them out of the boiling water into the colander, which is good, but if you're serving it warm you want to keep that to a minimum and have the "dressing" ready to apply as soon as you do. In my experience white and red potatoes seem to work best, with the ever generic russet pulling up behind. I don't have a massive lot of experimentation with different kinds of potatoes, so maybe those cool purple ones would taste good, but somehow the idea of purple potato salad just sounds...well, I think I'll stick with white thanks.
A big help is having non-stick pots, although I've found that will
not always stop things from sticking. You can drop a little lemon juice
in the water to break up the starches, but really, just let it boil.
Since I tend to make a lot, I use big pots, but either way, make sure
there's plenty of room for the potatoes to boil and cook, at least a
good 3 inches above the food. Another way to reduce the foamy starch at
the top is to soak the cut potatoes in some cold water for
about 30 minutes before cooking them, pour that cloudy starchy water
off, and cook them in fresh water.
So when you go to the store, white potatoes aren't the same as "Idaho" potatoes, which are typically russet. Russet potatoes have that thick brown skin that when you scrub it little flakes like fish scales will fall off into your sink. White potatoes have thin skins, like the red ones, and just need scrubbed up before cooking. Peeling them is more or less just wasting potato as the skin is so thin a peel is mostly inside "meat." Once washed, I tend to cube them up about the size of postage stamp, maybe 1" on all sides. Much bigger than I cut for say hash browns, which are typically a bit smaller than the size of the keys on my laptop - say 1/2". (But square, not flat! LOL) Pick out about 6-10 of the biggest ones depending on how "big" they are and wash and cut them carefully.
You want to cook the potatoes until a knife inserted into a nice big piece will not pick it up out of the water. The potato slides off. You do not want them to cook until they're falling apart though. This is the biggest problem with russet potatoes, they tend to break apart - that great quality that make them amazing baked potatoes and potato soup makes lousy potato salad.
Now that you have perfect potatoes, here's what to put on it.
1 cup Mayo (I like best foods - PLEASE don't subject your guests to miracle whip, it's NOT mayo!)
2 Tablespoons of DILL relish
1 stalk of celery from as far inside the plant (the nice small soft stuff with few threads, NO leaves.)
1/2 cup of Dijon mustard or "Stone Ground" mustard
1/2 teaspoon of paprika
Dice up the celery nice and small so it's not competing with the other flavors in each bite, just gives a little crunch. Or leave it out if you don't want crunch. You can add a little more mayo or mustard to your taste, you can mix in the paprika into the mix, add it as a garnish, or do both, and you can substitute sweet relish for the dill, but I prefer the dill. A good addition to this is bacon, too!
As soon as your potatoes are drained, either from the boiling or cold water, throw on the dressing and toss gently but well. Make sure the potatoes are all coated, a big bowl helps with that. Try to have the dressing ingredients all mixed together before you add the potatoes, it just seems to mix better. Serve warm or chill well and keep cold. Enjoy!