Maybe it's a good opportunity to travel along Trans-Siberian way? Making 1-day stops in Vladimir (with a tour to Suzdal), Nizhniy Novgorod, Kazan, Ekaterinburg, Ulan-Ude (maybe with a tour to the Baikal). Then take Trans-Mongolian train till Bejin. I think it's possible to do within 14 days. Bet it will be unforgettable.

I did not see the Gobi Desert in the winter. I did the Ulan Bator to Beijing route in October, 1984. I saw no snow. I did see quite a bit of snow in late May, 1978, my first trip on the Trans-Siberian.

All of this is recommended. Do it while you can. You will not regret it.

You don't necessarily book everything in advance, part of the visa application process for Russia, China and Mongolia (I don't know about Vietnam) you will need some sort of Letter of Invitation (LoI). These list things like when / how you will enter country, where you will stay, where you will go, where/when you will leave. These LoIs are not checked once you enter the country, so you can in reality vary your travels as long as you enter and leave the country within dates on visa.
I think from what you say you are not travelling on Trans Siberian, but travelling on Trans Mongolian (Beijing to Moscow via Mongolia)? Doesn't really matter as far as visas though.
Its pretty easy to book trains online for Beijing to Moscow and beyond; agencies like Real Russia are very good but of course charge a high premium.
All in all you will need some idea of dates you are entering and leaving each country before you apply for visas.
As far as Russia a good site from Australia is https://russiau.com/about-me/

Hi! So I can speak to a few of your questions, but not all.
First off, as mentioned 2 weeks is not a lot of time for the route you are considering. Trains and transit options run not as frequently in less dense areas of Russia not along the mainlines, but I can't comment on the exact logistics.

1. What is the most efficient way to link these destinations? I am aware of the sort-of route from Kosh-Agach into Tuva; of the usual bus/train routes between Biysk, Abakan, Kyzyl, and Krasnoyarsk; and of the TSR and BAM routes to the Baikal area. Are there other public/shared transit links that I am missing?

1.Yes, the TSR and BAM lines are where you will find most info on line. There are often buses/minibuses that will venture out of major cities to smaller towns, but as stated the timing of these would be very difficult to hit all the destinations you mentioned and enjoy them in 2 weeks.

More specific questions:
1. If we only had enough time to approach Lake Baikal from Irkutsk, would it be worthwhile? Especially compared to other destinations on the list?

Easily worth it. From Irkutsk take a marshrutka to Listvyanka (the closest and most developed area of baikal near Irkutsk), the ride only takes about an hour or two to get there. Once you're there, there are some really nice hostels where you could meet fellow travels. Baikaler Eco-Hostel is really cool, but it is a long walk up the hill.
There's lots of recreation opportunities by the lake (water activities, hydrofoil, smoked omul, market shopping, nepanarium where you can see the nerpa seals do a show, horse stables, hiking in the forest along the backpackers trail, baikal museum with underwater viewing area, etc.)

1. As far as I can tell, we could be in Kyzyl for Naadym. Should that sway our plans? (again, especially if it means missing out on another destination?)

I've heard naadym is a rough time to travel in Mongolia because of overcrowding and everything booked, but Kyzyl would be less crowded I imagine. If it were me I would try to make it work if I could, because I'm sure it would be an interesting cultural experience. Really depends on what you want.

From this, you shouldn't have any issues as two females, from my experience russia is a very safe place for travelers of all ages, genders, etc.
Not knowing much Russian is the bigger issue. The areas you mentioned stray far from the main tourist areas of the trans-siberian. I can guarantee you the vast majority of tourists you encounter will likely be Russians, if many tourists at all. So don't count on anyone speaking English anywhere. Anywhere outside of Moscow/St. Petersburg and to a lesser extent some university cities like Kazan you will likely encounter very few Russians who speak English.
Couchsurfing is excellent in Russia. Set it up in advance and find hosts that can speak English. They'll likely be a good resource for your ventures and possibly help you along the way. Hostels are also VERY cheap... never paid more than 800 rubs for anywhere I stayed, and typical was like 500-600 rubs.

I can offer some more specific suggestions if you're interested in going to some other places. Ie. Krasnoyarsk is a great jump off point for day-hikes into Stolby National Park, which is highly underrated imo.

All in all props to you for planning this trip! Sounds like you've got some good footing on getting the logistics down.

A colleague at my office has family in Ukhta and travels there every couple of years. By siberian standards it is a pleasant city, with better incomes than average due to the oil and gas industry, and the climate is not too bad. There is a university, some schools and parks, a giant "Magnit" shopping center etc.
Possibly you can visit the museum about the history of the Gazprom pipeline.
Check out the videos on youtube:
Ukhta presentation: https://www.youtube.com/watch?v=71zAQQP77JE
Gazprom history video: https://www.youtube.com/watch?v=GXG1ArEYkwQ

You have various parameters to take into account. First, length of the visa: if you are on the standard tourist visa, it is 30 days and not a day longer. Don't count on extending it, BTW. Second, how long it takes by train from X to Y. If you decide to break up the journey, you need more time, obviously. Third, the weather. That is a tricky one.

October is already a bit late in my view. You have to think of the weather in Russia/Siberia as being on a par with Scandinavia: I remember a weekend in Stockholm in mid-July some years ago and the temperature was around 14 or 15 degrees C.

I flew out to Japan (3 weeks there), got the boat to Vladivostok (interesting port city, BTW), then the train, and flew back to the UK from Moscow. Vladivostok has a micro-climate: rainy and unsettled in June, and it was. In Siberia, otherwise, in June, the weather was dry, sunny and warm (or hot). In the Urals and European Russia, it was unsettled and rainy, but everyone in Russia says June 2017 was rotten and unusually so, weather-wise. The average temperature fluctuated between 15 degrees and 25 degrees C. It was mostly the rain that was occasionally awful. I remember a day in Ekaterinburg where it rained non-stop for 24 hrs, and my arrival in Moscow which was apocalyptic with lashing rain (I do mean bucketloads) that went on for 8 hrs or something, non-stop!

Check the temperature charts but it may be chilly in European Russia in Oct., and cold or fairly cold already in parts of Siberia. In winter, in Irkutsk, with global warming, they routinely get == 35 degrees C against the -- 50 or -- 55 degrees C they used to get!

I am also from Chicago and have taken the Trans-Mongolian twice, the Turksib twice and the Trans-Siberian 5 times. Summer or winter is fine; I think winter might be even more magical.

I am a big soccer fan but if you just black out the dates for the Cup you will be fine.
The quality of the trains and the dining car have gotten much better, even in the last 2 or 3 years.
Vladivostok is a beautiful, sophisticated city; Ulan-Bator is not. But Mongolia is fun and the Ulan-Beijing link takes you across the Gobi Desert. This provided one of the greatest star shows I have ever seen.

So, UKEnglishTeacher, I was actually surprised that Russia was NOT as racist as I was led to believe.
In fact, I would say that I did not find Russia to be racist at all. I stayed there for a month, and besides the Caucasus, I went to Saint Petersburg, Moscow, and New Siberia.
Certainly, I encountered more racism in the United States and France and Estonia than I did in Russia which was actually one of my best trips ever. :-)

I would disagree that Chechens were racist. This was not what I intended to portray in my write-up. Essentially, I found Chechanya to be overly insular and provincial, and it was this, more so than racism per se, that contributed to my unpleasant encounters.

I can't comment on the unfortunate situation with LGBT persecution down there as I did not witness it myself. Nor would I say that Chechens are inherently violent, but I'm sure they could be when provoked as quite a number of men do walk around with switchblades and pistols...things I saw with my own eyes. :-)

Hope this clarifies?

It does, a little. See, I actually LIVE in Russia, and have done for 3 years. While tourists rarely see the racist side of things, I can guarantee you those who do experience it all the time, ESPECIALLY those of Central Asian descent or 'Caucasian' natives (by which I mean the southern Russian regions like Dagestan, Chechnya etc and into Georgia, Armenia and Azerbaijan). While Russians are not going to be overtly racist as such against blacks, they certainly have their prejudices, I've known black Americans/Brits etc to be refused work seemingly based on their race and whatnot. It's all luck of the draw, after all, I just returned from a business trip in Yakutsk and the office I was at actually had a Jamaican woman working there who said she has had no problems at all there (even though people ask what language they REALLY speak there lol)

Again, the insularity of Chechnya is basically why the rest of Russia dislikes the area, particularly with what they are known to do in say Moscow (which can involve, for example, firing guns in the middle of the city to celebrate weddings). This part of Russia is basically seen poorly by the rest of the country, which is actually partially where the racist attitudes of Russians can stem from as well.

As for the LGBT thing, of course, NO ONE in Russia, bar the very few who back them up, as well as LGBTs themselves, will ever comment on such things. Russians prefer to never discuss anything about it - it's the one topic that I can guarantee will cause a student of mine to divert away from, even if they are completely OK with LGBT people. Frankly, you're extremely unlikely to ever encounter any anti-LGBT things happening either, particularly in somewhere like Chechnya where they do it all undercover anyway.