Something to keep in mind is that, assuming they follow Stormblood's precedent and not Heavensward's, the new Jobs (whatever they may be) will be available outside the region it's "native" to and at a level below what's necessary to enter 5.0. DRG was picked up before entering Ishgard, and both SAM and MNK are picked up well before reaching Doma / Gyr Abania (SAM is technically Hingan flavor as well, but I digress).

... so something like Cid giving you a Gunblader Soul Crystal and mentoring you for a bit, then moving onto Lucia, then Gaius when we reach the 5.0 areas... isn't too farfetched, I don't think.