You still unlock the quests by receiving the letters, what's changed is that in order to receive the last letters for the quests, you need to change who your lead party member is. Most of the letters should be available after you acquire the fourth crystal.

Letter - Party Leader ~ Any other special condition

  • Topapa - Luneth ~ Onion Knight quest after fourth letter.
  • Takka - Refia ~ Need to go to Eureka to get his fifth letter to unlock the Ultima Weapon quest
  • Sara - Ignus ~ Ultima Weapon sidequest
  • Cid ~ Must meet the Legendary Smith to get his final letter for the Ultima Weapon sidequest
  • Four Old Men ~ Defeat the summons Leviathan, Odin, and Bahamut as well as collect all the treasure in the Sunken Cave to get all their letters and open the ??? Dungeon
  • Alus - Arc ~ To get his final letter, you have to reach Job Lv. 99 for a class and have their Master Item created by the legendary smith. Needed for ??? Dungeon