I had similar thoughts along these lines. Stuff like giving melee classes all their weaponskill combos at level 1, or giving each of the weaponskills quickly as they level up, so they can get a feel for the rotation. Then, at level 30, they get extra stuff related to their job.

Using Gladiator as an example, give them Fast Blade, Riot Blade, Rage of Halone and Goring Blade before level 15. Reduce Goring Blade's initial potency below Rage of Halone's and maybe even reduce the potency of all of the weaponskills by half, so enemies can survive longer to actually get through the whole combo and let the DoT tick for a while. At level 30, give them a neutered version of Requiescat that's only an oGCD that does more damage with the more MP you have; this'll teach them to use it when their MP is high. At level 35, give them Holy Spirit, so they can see that it does a lot of damage and is worthwhile to use, but you should use Requiescat before it so you get the most damage out of that. Viola, by level 35, players can have the basic rotation of Paladin down.