Hola Stendelis:
La idea del compañero gnzsoloyo me parece bastante óptima, hay algunas otras formas de obtener el mismo resultado, pero debido a las dimensiones de tu tabla puede que sean más lentas, pues involucran subconsultas y agrupaciones. Por ejemplo, con los datos que ponías de los nombres y el pelo obtuve una consulta algo compleja pero que funciona igual y la dejo por si la quieres probar, pero sigo creyendo que la lógica de gnzsoloyo es correcta
Código:
select distinct T1.country, T1.city from locations T1 inner join
(select city, (select count(distinct country) from locations T2 where T2.city = T3.city) total
from locations T3
group by T3.city having count(*) > 1) T4 on T1.city = T4.city and T4.total > 1
Saludos
Leo