Требование иметь два ключа сравнения делает решение нетривиальным, но, тем не менее, вы можете указать порядок сортировки, просто составив компараторы, возвращаемые вспомогательными методами, что избавит вас от необходимости писать собственную реализацию.
Ниже показана потоковая операция со встроенной компаратором, которая выполняет необходимый выбор.
List<Map.Entry<String, Integer>> result = map.entrySet().stream()
.sorted(Map.Entry.<String, Integer>comparingByValue()
.reversed()
.thenComparing(Map.Entry::getKey))
.limit(2)
.collect(toList());