I started over myself a few days ago, leveling is super quick. You can start Rhapsody missions right away, but can not finish them until you reach a certain point in other missions.

Trust Magic can be used to spawn NPC's to make them fight alongside you. I think this unlocks at level 5. You can have up to three to start with, but can unlock two more spots while doing Rhapsody. As a new character your trust choices are limited, but with the login campaigns going on it is easy to get some good trusts within a few days.

There are really easy ways to get huge EXP bonus. You can do the first few Rhapsody missions (just a bit of running around, no fighting involved) to get a key item which gives you 30% EXP boost, non-stop! There is currently also an event going on you can do within a few minutes to get a Kupofried trust, which gives you a standard 20% (not 100% sure on the % here) EXP bonus as long as you have it out. Combined with some EXP bonus rings leveling is really quick.

To avoid new people feeling left out and having no gear and/or items to buy from AH SE installed some new moogles that sell lots of shit (like prism powders, silent oils, low level gear etc. etc. etc.).

Oh! Also have RoE now which you can compare to Challenge Log of FFXIV, but with good EXP rewards