When I first enter FAF i thought it looked very hardshaped, didn't like the UI very much and its old looking. Anyway I started to fall in love with the possible things you could do, lover your gunships below shields etc.
So remembering my first interaction with the game that would be nice to do.
- Update UI to look more modern
- Explain features in the game (example that you could block a nuke with a scout but its very rare and very hard to do)
Playing with some friends with different level of skills, some feeling more newbie like. A tutorial would be good, limit them to do movement, patrol, etc unlocking a feature at the time. Help them zoom out to let them learn why its good to play more macro than micro.
Also people have trouble learning what to do right, for example when playing chess, it can be analyzed to point out errors, that might be hard to do by data but simple things like reclaim when mass stalling or something would help them feel progress about themself.
As you explained earlier, people in learning progress have it hard when playing against experienced players, hopefully the AI tournament can help pointing out which Ai to play against at certain skills to help improving at the game.
To avoid the custom game lobby looking like it does, full with Astro and Dualgaps, maybe a cue to match people on a random map would be good, like you do on most games, more queues for ladder and global games. A map there people don't have the exact build order and can do errors so the low rated players doesn't get too crushed by T3 bomber at min 10 against exeprienced players.
Achievements are good aswell, help them try out new stuff, but you don't feel as awarded like you would in another game. For example league rates players in game and keep progression tracks on you and shows that you are doing some progress (maybe too much which ends up being ignored instead).
Maybe also more resets for player giving them a chance to come back in rating, specially players under a certain rating. For example it wouldn't feel good to have a negative rating. Maybe reset some players around a certain scale. For example rate the bronze, silver, gold. And then you come abobe 1400 rating you could have your rating shown instead, so it doesn't create fear for new players to play 100rated vs 300rated player, call them both bronze instead and they wouldn't know and do their best.
For example I played a player who did very good trying to snipe me with earlie bombers, I managed to survive but were damaged in my expansion, but it was his shot and he quit since he thought it would be impossible to beat me even if I were only like 100-200 rating higher than him.
As for the queue for random game, if low rated players match you could fill with some Ai without them knowing what is what. Flaming a Ai may seem very stupid and hopefully that removes some toxic specially against lower rated players.
And since all games (pretty much all games) are rated games, people find it easy to pray on the weak when losing. So maybe a non-rated queue playing on a random map like playing like crap would be good for new players.
Hope you find a way to introduce new players!
Best of luck!