The Valencia Cathedral was called Iglesia Mayor in the early days of the Reconquista, then Iglesia de la Seo (Seo is from the Latin sedes, i.
What was the Cathedral's name from early in the Reconquista? 
Iglesia Mayor