I'll go with the obvious. It's a Chocobo.

You might never find them: They are optional.

Big one usually finds you: Midgar Zolom is the reason most people get one.

The likes of you won't differ my brother and me: There is no perceptible difference between the Chocobos, yet there is a great variety that can be caught (poor, good, great, etc).

How to beat, how to catch: Choice of what to do when one shows up.

Hurry up or I'll be gone: They run away shortly into combat.

Because you're no match: No matter how powerful you get, you can't kill them.