> Для btree - как ни крути, надо полагаться, что квадратик больше другого

ну вот и получаем неопределенное поведение.
imho, правильнее оставить btree для численных и приводимых к ним данных (ip6 адрес отправить тем же лесом, поскольку тоже совершенно неясно, что такое "больше") и, может быть, для национальных алфавитов с жестким ограничением на один алфавит (A > А? Или < ? Или = ?) в остальных случаях это, очевидно, бег по граблям и надо сразу бить автора такого запроса по лбу, не дожидаясь, пока он государственную базу загранпаспортов на таком решении соберет.

С тем же ё - Леша > Лёша ? Или < ? Или = - но если так, каким сумасшедшим collate это должно описываться, даже если букву сто лет как не двигали?

При этом для индексов во многих случаях collate не то что не нужен, а замедляет в разы работу - на самом деле в том use-case что у этого приятеля, скорее всего вообще можно было с легкостью использовать null-collation, отсортировав все буквы просто по номерам в unicode, вряд ли это символы хоть какого-то алфавита.

> Юникод-консорциум это учитывает, обновляет collation-ы и присваивает им новую версию.

поапгрейдил libc - индексы в базе превратились в тыкву? ;-)