I had met Cat at 4th St. two years ago, but despite my best intentions none of her books had made it to the top of the pile before. She's one of those writers whose work gets described as "lush" and "lapidary," both of which often translate into "too visually focused to hit not-very-visual mrissa just right." Deathless both was and was not that: it's a book with a lot of visual imagery, but a lot of its sensory suite is more where I live (there's a lot of food/taste stuff here), and I think its setting inherently provides balance so that the visual stuff stays vivid without getting overwhelming for someone who is really, really not visually focused.
The setting was a major, major draw of this book for me. It's in the time frame where you can't say exactly where it's set: St. Petersburg? Petrograd? Leningrad? All of the above. And that time and place, that setting: it is not nice. It is vivid and fascinating and very well-handled in this book. But in addition to being set in Russian fairy tales, this book really is set in Leningrad 1942, and that means that people will die when you would really prefer that they did not. And that means that whenever another fantasy of this type might be wandering off into abstraction, we are pulled up short with a bump. The setting grounds and roots the fairy tale elements: life and death are life and death, not just guys in funny hats.
There were a few places where Marya's motivation struck me as more fairy tale than grounded in that Leningrad, but that was sort of meta-motivated: we see in the very opening that this is not a girl who has had a chance to live in a world without the fairy tale trappings, even as she was queuing in the bread line with her ration card. Fairy tales have enveloped and pursued her, and so the story begins and ends that way, but the tales aren't bookends, they're pervasive. They permeate.
I would be interested to hear what people who are more familiar with either Communist Russia or Russian fairy tales had to say about this book, because the stuff in it is mildly familiar to me, the kind of familiarity one has with things one has read a bit about, and I know that I have friends and acquaintances who lived and breathed some of these things. And everybody's take on the myths of their heart is different--people who are very knowledgeable of the Norse myths I love have done very, very different things with them--so I'm hoping that somebody speaks up with some thoughts on Deathless from a rather closer angle than mine.