I hadn't got around to looking up either, but if someone had asked me to guess, I'd have gone with зимний солдат for winter soldier, and apparently the actual spider is called чёрная вдова in Russian (I just looked at the wiki page on Russian wiki), so for once I think you're golden with those two! (If you look at Russian wiki it'll have it as a plural, чёрные вдовы, but that's when it's a species name.)

I imagine any page in Russian will use the title Marvel gave to TWS, but зимний солдат seems logical to me. зимний is the adjectival form of winter, and I know Russians do use that metaphorically, similarly to how we sometimes use it in English (ie it doesn't have to literally pertain to the winter season), so I think however you take its meaning in English, that's a pretty good Russian rendering - with the I am not a native disclaimer firmly in place ;)