You should do the Wutai side quest before the Gold Saucer date sequence if you can. If I remember correctly, Yuffie gets a lot of affection points (10?) if you complete her quest in Wutai, so if you want Cloud to go on a date with Yuffie, you pretty much need to do the Wutai side quest as soon as you get the Tiny Bronco. If you want to wait until Disc 2 or 3, it's up to you, but by that time, many of the fights will be really easy.