Is it better to go abroad with euros? What is the best kind of place to exchange currency?
Avoid exchanging in airports, hotels and other typical tourist locations as you get much worse rates (this is true not only in Russia).
Only banks can run currency exchange operations in Russia. Find any regular bank outlet and exchange there. Euros are as common as USD, thus there won't be any problems. Be prepared that no one will speak English or any other foreign language in a bank (even if it's an international brand).