According to Eorzean Lore, the Chocobo first appeared in the woods outside a desert somewhere around the Final Fantasy II timeframe. Because all chocobos come from eggs, this undoubtedly proves that the egg was first.