Actually, you can challenge Cid on disc 1. Before heading to Timber, I think... if I remember correctly, he says he's too busy before the Dollet misson. Maybe not. *shrugs*