Slavic folklore included female bogatyr called polianitsa, who are known to be as brave and strong and skilled as the bogatyr, and who often rescue their husbands. Dobrynya "met" a polianitsa named Nastas'ya Nikulichna when he saw her riding her black horse across he plains. (Without explanation) he fired an arrow at her that struck the side of her helmet. The strike had no effect; the arrow bounced and fell to the ground. He fired another with the same result. A third arrow finally caused her to stop and look around.
She rode up to him, grabbed him off his saddle by his hair, stuffed him into her saddlebag, and continued her ride. After four days, her horse stumbled, complains to her that he was carrying too much weight. Nastas'ya then pulled Dobrynya out of her pouch, asked him who he was, and gave him her terms: if he were older than she, she would kill him; if he were younger, she would treat him like a brother; if they were the same age, she would marry him.
Dobrynya did not want to risk revealing anything, so he refused to talk. Her horse recognized him, however, and identified him as Dobrynya Nikitich who was her age. Nastas'ya said they should get married, and they rode to Kyiv to make it happen. Prince Vladimir attended the wedding feast, which lasted three days, and Nastas'ya went to live with Dobrynya's widowed mother, Amelfia Timofeyevna, while Dobrynya went to fight a war in Lithuania.
While Dobrynya was away for many years, Nastas'ya (believing him dead) agreed to marry Alyosha Popovich (the second of the three best-known legendary bogatyr). Dobrynya was not dead, however, and learned of the wedding plans. He rushed back in time to attend the wedding disguised as a minstrel. After singing for the couple, he revealed himself, forgave this wife, and threatened to kill Alyosha. He was stopped by the third legendary bogatyr, Ilya Muromets. Dobrynya and Nastas'ya then lived happily ever after, agreeing to never speak of or to Alyosha ever again.
Whew.
There were actual women performing legendary acts in history. Vladimir's grandmother was one of them, in fact. Another was a 1st century British queen—a little early for the Middle Ages, but mentioned in medieval literature—Boudicca. Let's talk about her next.