Надо отталкиваться от компании. Со временем сразу можно научиться определять: в какой компании лучше всего зайдет "Звезда по имени Солнце" и Шевчук, в какой надо играть самые авангардные песни Федорова и Аукцыона, а где - Radiohead и Тома Уэйтса. Соответственно, достаточно выучить штук 5 песен для разных компаний и всегда быть наготове.
По моему опыту, есть универсальные произведения типа "Такие девчонки" Мумий Тролля, "Выхода нет" Сплина и "Creep" Radiohead. Больше половины любой компании всегда знает хотя бы одну из них.