You don't need to create a new character. You want to do a bunch of leveling of classes other than your main anyway, for cross-class skills.
As mentioned, having Cure is *really* helpful for every other class.

At this point, I'd get CNJ to 12. You only need 10 to unlock the ability to change classes, but you get Raise at 10 which can be another great cross-class skill when starting out.
After that, you have to finish the storyline quest at 15 to get access to other cities (you could run there now but there it isn't necessary). Since you will eventually have to get archer to 15 for black mage, you could either get far enough with conjurer or switch to archer and get to 15 with that.

You should also go into the Party Members section of the Social menu, select yourself and edit your search info. There is a new online setting for New Adventurer. That will let helpful people find you more easily.