When is it smart to do a job change? Should I max the level of a character first?
There is no penalty for doing a job change at any point. You can always revert back to a previous job, although the jobs all level separately, so if you intend to use a character you will want to level up all of their jobs at least a little bit. You definitely don't want to wait to max out a character before doing a job change, because until you get to very late game it takes incredibly long to level a character to the max, and in the meantime you would benefit from the skills they learn from the other jobs.
As Mistouze says, at level 20 of each job you unlock an extra skill slot (used to equip skills from other jobs), so it is generally not worth unlocking a new job until you have gotten to 20 on your current job. 35 will get the third skill for a job, but if you are early on it takes a while to get to 35, especially before you unlock Metal Zones 2 and 3, so I wouldn't necessarily hold off on a job change for it.