There are a bunch of Russian restaurants in CDN. You could search this board for some info on them. I have no experience with them. I've only been to Le Georgia which is Georgian but does serve some Russian fare. It's a great restaurant though and certainly worth a visit.
Here are a couple of threads that mention Russian restaurants:
I ate at troika about 5 years ago after getting a $100 gift certificate for xmas. What I do remember is that it was a good meal, but as epikurien says, tough on the wallet.
I can't recall the details, but I do know that the price has kept me from returning (was in the order of $250 for two - although not OVERLY expensive, the place perhaps does not warrant these prices).
There's apparently an authentic russian resto on beaver hall hill. I think I read a review in Hour, but never tried that one.