You can get the benefit of cross-class skills while you're still on your base GLD class, before unlocking Paladin, and things like Pugilist's Featherfoot or Second Wind can be helpful there. Once you unlock PLD, though, it will be better to stick with it rather than Gladiator, as PLD has much better stats. As PLD, you'll only be able to use cross-class skills from Conjurer and Marauder, so those two should have higher priority to build up for cross-class skills than classes you'll only be able to cross-class from temporarily while you're still a Gladiator.

Conjurer is the one you need to get up to level 15 in order to unlock Paladin, but Marauder provides more useful skills for a tank than Conjurer does. (For instance, while it's possible to cross-class CNJ's Cure spell on your GLD or PLD, it's effect is based on your Mind stat, which is really low for tank classes, so it won't accomplish much compared to what happens when a caster uses the same skill. Occasionally useful for low-level soloing, but becomes less and less useful as you go up in levels.) Foresight (MRD level 2) and Bloodbath (MRD level 8) will be more useful to you.

As for when is the best time to get these, it's pretty much whenever you want. But since some of the nice useful ones are acquirable at low levels and so are fairly quick and easy to get, I think it's worth going for them early when you'll have the most time to make use of them. You can wait until later to pick up some of the higher-level cross-class skills, but maybe doing the first 8 levels each of CNJ and MRD early is a good idea.