I'm from Ul'dah myself and got the spell after I completed the starter quest. You have to talk to Momodi and she gives it.
I would imagine it being the same in the other cities. Finish the starter quest and see if you don't have it then. Also to note, I got the conjurer and THM versions of the spell at the same time while being on conjurer the whole time.
Maera, Mithra on Cerberus