Your first and third questions are actually related. You can find how to start the quest chain on the lodestone at http://na.finalfantasyxiv.com/lodest...=3&category3=6. It all begins with the Legacy of Allag quest, which starts at Mor Dhona (21, 8); the NPC to start the quest is Outlandish Man. Cloud of Darkness is the final boss of the Crystal Tower trilogy, when you and 23 others go to the World of Darkness.

Gilgamesh, as well as several other prominent Final Fantasy figures from past games, can be challenged through the Hildebrand quest line. Details of the questline can be found at http://na.finalfantasyxiv.com/lodest...9&category3=19. The starting NPC is Wymond located at Ul'dah - Steps of Nald (9, 8).