Não faz sentido ordenar por uma coluna que não faça parte do
distinct selecionado colunas. Como você não está participando de uma coleção, seus registros serão distintos de qualquer maneira (pelo menos o PK será diferente), você pode apenas omitir distintos:
select distinct city
from City city
where city.id is not null
and upper(city.name) != upper('Unknown')
and city.state.id =:stateId
order by upper(trim(city.name))
Em geral, quando realmente há duplicatas no conjunto de resultados e você deseja eliminá-las, pode fazê-lo com uma subconsulta:
select city
from City city
where city.id in (select c.id from City c join c.someCollection sc where ...)
order by upper(trim(city.name))
O outro benefício dessa abordagem é que provavelmente é melhor em termos de desempenho, pois
distinct A criação de linhas geralmente é uma operação cara no banco de dados. 
