I think I have a great Idea that encourages freedom for new players, while also making sure they have supervision. Additionally, it can be a proving grounds for Aspiring GM's.
What we do is have Players and/or GM's volunteer with ideas for 'Quick plots' and make themselves available to oversee these quickplots. What you need to do is have a list of these quickplots with a very basic description, listed with benefits and risks, as well as the hosting GM. When a player finds one of these quick plots they like, they simply PM the GM in charge of it, and the two of them can begin roleplaying.
Additional characters should be able to join, depending on what the GM thinks they can handle. But, these plots should try to be fairly short, like a simple event or Mission, wrapping up in a single thread and then leaving the participants free to find another Quick-plot mission, or perhaps to try and join a major plot.
The benefits for a New player are simple: It allows characters freedom of choosing what they can do, while giving them tangible, IC rewards, as well as helping them to learn the setting in a supervised setting without forcing them to commit to a specific plot.
For the Players and GM's that volunteer their time to facilitate this, there are also benefits, namely for veteran players who want to GM but have little experience: It gives these players practice at GMing without forcing them to commit to making a major plot, while allowing them to influence the setting in both major and minor ways. Additionally, if they choose to use PC's to facilitate these Quick-plots, their characters might also be allowed to reap the in-character benefits of such events.
So, basically, it's a Win-Win-Win-Win situation.