To be able to do all quests (or most of them) you need to be able to do jobs. To do jobs, you need SP and AP. Instead of +5 SP, you should go for an item that provides you +6 AP.
So take soldier class and find here on the forum any (classic) alljobs build. We still don't know what impact will the next update with new set items have so don't ask for a new alljobs build. The next update will be added soon.
The fastest start in this case will be pure leadership, later you'll put points into other S/A. Make sure you chase AP/SP reward quests, don't waste time on others unless they give plenty of XP. All crappy nonAP/SP reward quests you skip, you can solve later on level 120 with any build.
And make sure you gather the whole gentleman's set. Including the new item that will come in the next update, since with that set, you'll have +100 laborpoints bonus. On all jobs.
Don't waste time on cash jobs, you'll have enough cash for anything later. Try to work on jobs that provide nice XP and drop nice (expensive) items. Also don't waste time on gathering questneeded products if those are on low XP jobs. Buy them on the market instead.