Erro do SQL Server Conversão implícita de porque a ordenação do valor não foi resolvida devido a um conflito de ordenação.

Você provavelmente precisaria de COLLATE em ambos os lugares.

Select City COLLATE DATABASE_DEFAULT AS Place, State, Country FROM DEPT1
UNION ALL
Select '' COLLATE DATABASE_DEFAULT AS Place, 'Arizona' As State, Country FROM DEPT2

Edit:Você pode precisar dele em todas as strings se conseguir em um só lugar

Select
    City COLLATE DATABASE_DEFAULT AS Place,
    State COLLATE DATABASE_DEFAULT AS State,
    Country COLLATE DATABASE_DEFAULT AS Country
FROM DEPT1
UNION ALL
Select
    '' COLLATE DATABASE_DEFAULT,
    'Arizona' COLLATE DATABASE_DEFAULT ,
    Country COLLATE DATABASE_DEFAULT
FROM DEPT2

Editar2:

Isso acontece porque seu agrupamento de colunas provavelmente é diferente do agrupamento de banco de dados. Portanto, "City" tem um agrupamento, mas as constantes de string têm outro.