Actually, the idea of limiting the player's options until certain early progression points sounds ~incredibly~ good. The biggest complexity in AI War, in my option, is the first five minutes of the game: You are handed four dozen options, and you really have no idea what any of them do or what you really need, and by the time you have read through half of them
oh crap it says ships are attacking me and I haven't built anything yet (my very first game of AI War right there...).
Starting the player off with nothing they can really do except build fleet ships and scout, and then unlocking everything else piece by piece at early progression goals... that would work really well. I am not just speaking theoretically here, either; consider X-Com (1 and 2) and, for those who have played this rather obscure game, FortressCraft. The tutorial is not a button you click on separate from the main game to do at your leisure; when you start a new game, the campaign starts with the tutorial and then the tutorial seamlessly transitions into the "real" game.
Also important: There is a "skip tutorial" button.
I really think something similar could massively reduce the barrier to entry of new players.
You could also kinda follow Binding of Isaac's lead, with having certain in game achievements unlock new out of game features. That would help with how overwhelming the lobby is. Or maybe just, the very first time a player enters the lobby, it tries to start them on a simple-settings game. NOT, I should mention, a short standalone tutorial. That is, I think, where a lot of tutorials fail in RTS games - they feel like a chore because after you finish them, you have to start the game over from the beginning again to play the "real" game.
I skip tutorials in most games, but both X-Com games got me to play through the tutorial by making it part of the actual game, instead of something I have to independantly pursue. If the tutorial pulled another note from XCom's playbook and introduced some lore/storyline at the same time, that would be even better.