Highly untraditional with real BBQ, but I love French potato salad: cook sliced potatoes until just done (under 10 minutes for 1/4-inch slices). Drain, saving some of the cooking water. While still warm, sprinkle with a vinaigrette of olive oil, white wine vinegar, chopped shallots or very finely chopped onions, lots of chopped herbs (parsley, thyme, chives, tarragon, whatever!), salt and pepper. Fold gently to combine. Serve at room temp.
Or of course there's a good ole' potato salad with cubed potatoes, mayo + mustard + yogurt + a little vinegar to thin it, chopped sour pickles, sweet pickle relish (I like BOTH), chopped celery, chopped onions, parsley, and chives or scallions (I like mine oniony).
I also like to mix cole slaw vegetables (cabbage, carrots, celery, onions, cucumbers) with an Asian-style dressing of soy sauce (just a little), rice wine vinegar, sugar, sesame oil, ginger, garlic, and some hot pepper flakes. Again, not traditional, but very tasty! And both this and the French potato salad balance nicely against the wonderful fattiness of good bbq.