I wonder if just adding “I am a beginner” as a checkbox option while starting a new account would help things. Players who aren’t beginners could reasonably start at 13k and get to their real ranking within a few games. Most players will probably be in the 7k to 17k range, which won’t require long to stabilize, and having a dual entry point system will keep beginners from entering as Dan-ranked players and messing with that part of the game pool.
For beginners, they could be given a Glicko rating of 1500, as per usual, but a ranking of 25k, (as has been suggested by several other people), which would start them at the bottom of the rating pool for actual games. That way, beginners could play other beginners, without needing to get beaten down from 13k to 25k, first. Taking all of the true beginners out of the 13k pool would at least somewhat lessen the instability at that rank, as well.
Some players will sandbag and start themselves off as beginners instead of 13ks, but as they’ll have high uncertainty and an actual rating of 1500, they’ll only be there for a few games. Regardless, it seems likely than fewer people will be mis-rated through intentional sandbagging than are through the 13k default rating.
Finally, I do think it would be a good idea to preferentially auto-match new accounts with other new accounts. Doing so would at least provide some information as to where new accounts belong, before they get dropped into the general rating pool.