I didn't get to play in it, but a friend of mine ran a home game years back (during the 3.0 D&D days) where the players were basically apprentices. They knew they wanted to be wizards/fighters/clerics etc, but they had to basically work to find people who were willing to take them on and train them. He had a funny story about this player who wanted to have his wizard become an Evocationist, but the only mage he could find who was willing to take him on as an apprentice was a gnomish Illusionist...apparently the player was unimpressed, but the gnome was really excited at the prospect of taking on an apprentice.
Not sure how you want to do character creation, but perhaps start your game with your players going through Legionnaire training, have them spend some time fighting in the Legions and then they gain the Former Legionnaire background? You could start them with a maximum of 1 rank in a range of skills, and then grant further skills/talents as they go, up to the character creation max of 4...character creation meets RP