Before you go anywhere else head to Qu's Marsh and pick up Quina.

After that go east and cross the river to find the Chocobo Forest where you learn to call and ride chocobos.

Just a little further east is South Gate where you can find a healing spring, the Moccha Coffee and an Ether.