Final Attack- Complete special battle in Battle Arene (Gold Saucer)
HP<-->MP- Desert cave near entrance to Mount Coral (Black chocobo)
Contain - Buy expensive greens, then talk to white chocobo in Mideel, tickle behind it's ear (I think)
Alexander i know where to get it, i just can't remeber where the cave is- In the snow area where you use a map, it's awkward to get to so can't guide more.
Quadra Magic - Island cave along from Mideel (Blue chocobo)
Mime - Cave on Wutai continent (Green chocobo)

I forget the others at the moment.

The other flyer is in the Gold Saucer Hotel.


Haven't played in a long while so there could be errors.