I was just in Moscow two weeks ago, and had the same idea -- but little time to look around. I went out to the famous weekend Izmailovskii market in an eastern district of Moscow, and found a few fellows selling primarily Russian cameras -- Zorki, Lubitel, etc. As I don't speak Russian, and they had limited English (unlike the people selling nesting dolls!), I wasn't able to ask for 85mm lenses for my Kiev or Contax RF which is what I was after. I could ask for Leningrad RF cameras, but no one had any. I almost took a Russian 6X6 stereo camera for $130, but decided against it -- just as well, based on what I subsequently read about quality control on these cameras.
My experience, admittedly at just this one location, was that there wasn't a whole lot of quality product available. I sincerely hope you have better luck finding something of interest.