A generous dollop of horseradish.
I make patatas aioli, which is Spanish-style potato salad with garlic mayonnaise. I don’t really like any potato salad but this one. My friends also agree that it is delish, even that one time I put WAY too much garlic.
Saffron. A pinch stirred into the dressing makes it a lovely colour and adds that saffron hum. Noone will ever guess your secret ingredient!
This Better Homes and Gardens recipe is fantastic hot or cold. I add chopped red onion raw rather than roasted for a little crunch, and skip the celery 
because I love my picky husband. And though it seems weird: trust the corn. The roasted corn is the secret ingredient that adds that special something.
I don’t want to chance a violated copyright, so here is the link to the rest of the recipe: http://www.recipe.com/potato-salad-with-country-ranch-dressing/
Ingredients
3 lbs. round red potatoes, cut in 1-inch pieces
1 small red onion, cut in wedges (1/2 cup)
6 cloves garlic, minced
2 Tbsp. olive oil
1 cup frozen whole kernel corn
3/4 cup mayonnaise
2 Tbsp. cider vinegar
1 1-oz. envelope dry ranch salad dressing mix
1/4 tsp. cayenne pepper (optional)
1 stalk celery, bias-sliced
3 hard-cooked eggs, peeled and chopped
1 avocado, halved, seeded, peeled, and chopped (optional)
Salt and ground black pepper
Fresh Italian (flat-leaf) parsley, coarsely snipped (optional)
Me too.
And tarragon (only if available fresh).
Mine’s really simple… Drain a couple cans of new potatoes, little bit of dijon mustard, torn fresh spinach leaves. Adjust amounts of each to taste. Oh yeah, and sometimes some bacon. Stir, chill, and enjoy.
Maybe I misrepresented my dressing a little. It’s made with mayo and vinegar and sugar (I like it on the vinegary side though, not sweet at all though I’ve had it that way too) I’ve never tried a straight vinaigrette on potato salad. Might be interesting to try once at least.
Are you my mother? One of her potato salad variants (she has at least three) has bacon, scallions, and cider vinegar.
Asparagus and rucola.
Capers, feta cheese and/or strips of Swiss cheese, dillweed, celery seed, dijon mustard, shredded jicama, a dab of tartar sauce, minced bell peppers and chopped cornichons.
Not all of this stuff at the same time, mind you, but…
Solid.
My potato salad is mayonnaise free:
Olive oil, fresh dill, seed mustard, Dijon mustard, spring onions, red wine vinegar, salt and pepper mixed with hot potatoes and allowed to cool.
Finely shredded spring onions (all the white end and as much of the green as is tender) plus a little dijon mustard.
I think you call them green onions or scallions in the US…
Habanero Peppers (seeds and all).
I was hoping someone would say that!
I like to parboil chopped onions and red peppers when the potatoes are almost done, then I add a spoonful of Colman’s dry mustard to the Hellman’s mayo, along with fresh dill and salt and pepper.
My mother uses diced cooked cauliflower and folks rave about her “potato salad” I think she also puts Durkees in instead of mayonaisse or maybe just part of it.
Now I want potato salad.
Capers, yes. I also have a bottle in the refrigerator of tartar sauce that will probably sit there forever, so I add a squirt or two to the mayonnaise. Quite tasty, and it uses up the tartar sauce. (and I don’t think you can have too many eggs in potato salad.)
zucchini relish. It’s a hand made relish using my great grandmother’s recipe. my mom makes it about once every three years or so and gives me a dozen pint jars.
I make my potato salad just like my mother. No measuring, just drop in the amounts that look right. The recipe is simple: boiled and peeled potatoes, chopped hard boiled eggs, chopped chives, mayo, and the special relish. Absolutely not one drop of mustard of any kind is present. Seriously. Keep the French’s out. Gross.
My potato salad gets rave reviews from everyone (except a few of my in-laws who are dyed in the wool mustard potato salad people.)