Ошибки:
1 - сортировка всегда должна предшествовать другим операциям в записи, то есть
ref.OrderBy(KEY_PRIORITY).whereGreaterThan(key_priority, 1)
2 - startAt не определяет первую букву поля.
Есть два решения - либо вы тянете все записи с приоритетом выше 1(то есть просто
collectionReference.whereGreaterThan(KEY_PRIORITY, 1)
) и уже на клиенте отсеиваете все, которые начинаются не на "А", либо вводите дополнительное поле, например, firstLetter и помещаете туда для каждой записи первую букву. В таком случае запрос будет выглядеть примерно так:
collectionReference.whereEqualTo("firstLetter", "A").whereGreaterThan(KEY_PRIORITY, 1);
UPD: как попробуете дайте обратную связь получилось или нет)