i get yuffie at the earliest possible stage: wen u cum out of the mithril mine go to the forrest hugging the moutains which are near junon and get in2 a few fights,
it may take a while but she'l appear now and then.

which means i go 2 wutai and complete her side quest as wel as gettin leviathan + a cool weapon 4 cid as soon as i get the tiny bronco