It doesn't sound like you are playing the same songs in the same order every night, my normal advice for the "same old same old" syndrome of "dump fixed set lists and have enough material suitable for the audience you play such that you can cope with picking songs on the fly" may not apply!

I've had the same issue - play something new, get told off because you didn't play someone's favourite. Then again your "new" song could be someone else's favourite, you'll only find out by trying. Play the other favourite next time (and namecall the complainant so they'll feel special) and leave out something else!