Para que te funcionen las ñ, acentos y otros caracteres especiales como la ç, necesitas trabajar con UTF8. Esto en Ajax es algo obligado.
Entiendo por tu pregunta que lo estás haciendo ya, porque si no, no te funcionaría en ningún navegador...
Entonces lo más seguro es que tengas que hacer una limpieza en tus cadenas antes de compararlas. Así también te asegurarías que cuando alguien busca con o sin acentos le encuentre cosas. Por ejemplo, podrían buscar por "cádiz" o por "cadiz", incluso "espana" o "españa" deberían arrojar los mismos resultados.
Este código está sacado directamente de stackoverflow, que permite eliminar los acentos y otros caracteres (no lo he probado):
const str = "Crème Brulée"
str.normalize("NFD").replace(/[\u0300-\u036f]/g, "")
Devuelve "Creme Brulee"
Fuente: https://stackoverflow.com/questions/990904/remove-accents-diacritics-in-a-string-in-javascript
Con esa conversión sí que deberías obtener las localidades con las ñ y demás.