Quick Guide to:
Title Changing NPCs
Bastok Port - Tuh Almobankha (I-7)
Lower Jeuno - Tuh Almobankha (I-8)
Kazham - Eron-Tomaron (G-7)
Norg - Quntsu-Nointsu G-7
Mhaura - Willah Maratahya (I-8)
Rabao - Shupah Mujuuk (G-8)
San d'Oria South - Moozo-Koozo (K-6)
Selbina - Yulon-Polon (I-9)
Windurst Walls - Burute-Sorute (H-10)
Each NPC generally has the titles for quests related to the city they're in. The Amount of Gil you Pay reflects the Fame level requirement of the Quest. For example, with Burute-Sorute, 100 Gil I could get Crawler Culler. 500 I can get Heir of the New Moon.