Destroy is the only one I went to, it's got a really good seleksh. Boards are from 900-3000Roubles (30-100US), shoes are expensive, clothes are expensive, but wheels and trucks and the important things are not bad.
It's at Tulskaya metro station, which is three stops from Biblioteka in the centre (next to the Kremlin). Check a map, I think it's on the gray line. It's in a weird cool kid mall called roller something, you have to go a block west form the metro, a little tricky.
Most of the real shops have closed due to internet shops.
http://skateboarding.ru/you can translate shit, but go to Споты, to get directions to spots. I'd recommend Kaluzhskaya, Theater Square (front of Bolshoi) Park pobyedi, and Arbat for ledges. Gorki Park has two skateparks in it that don't suck...