Okay, so hear me out: diced apple in your potato salad. My preferred variety is Macoun, with one apple per six potatoes or so, diced roughly half the size of the potato chunks. It brings a nice brightness and a little crunch that's distinct from recipes that use celery. Spices usually used include paprika, chili powder, finely ground black pepper, and light salt.