-(Controversial) Give cross-class skills without leveling up alternate classes. Asking someone to level two side classes to 30 or 40 for their last few skills is quite a lot; you could offer a "sneak peak" of other classes by enabling the cross-class skills by current class level.
-Allow the new classes to be played earlier, even if the class quests don't kick in until 30. Leveling one job to 50 just to start your second job (that itself requires two 30-40 side classes) is a crazy investment for a new player that wants to try MCH/DRK/AST.