Brienne was never treated well by men. She was considered ugly and unladylike. Worse, she had been taunted and teased by men purporting to be her suitors.
However, Renly always treated her kindly.
It is revealed in A Storm of Swords that she first met Renly as a teen, and was smitten with him at first sight:
Renly Baratheon had been more than a king to her. She had loved him since first
he came to Tarth on his leisurely lord’s progress, to mark his coming of age. Her father
welcomed him with a feast and commanded her to attend; elsewise she would have hidden in her
room like some wounded beast. She had been no older than Sansa, more afraid of sniggers than
of swords. They will know about the rose, she told Lord Selwyn, they will laugh at me. But the
Evenstar would not relent.
And Renly Baratheon had shown her every courtesy, as if she were a proper maid, and pretty.
He even danced with her, and in his arms she’d felt graceful, and her feet had floated across the
floor. Later others begged a dance of her, because of his example. From that day forth, she
wanted only to be close to Lord Renly, to serve him and protect him.
Even after that, during A Clash of Kings once she joined him in his bid for the kingdom, he accepted her on her own merits, and bestowed upon her the highest honor she could have hoped for: he made her one of his own personal guards.
“Your Grace,” Brienne answered, “I ask the honor of a place among your Rainbow Guard. I
would be one of your seven, and pledge my life to yours, to go where you go, ride at your side,
and keep you safe from all hurt and harm.”
“Done,” he said. “Rise, and remove your helm.”
From her reaction, it is obvious just how much this means to her:
And yet, when Renly cut away her torn cloak and fastened a rainbow in its place, Brienne of
Tarth did not look unfortunate. Her smile lit up her face, and her voice was strong and proud as
she said, “My life for yours, Your Grace. From this day on, I am your shield, I swear it by the old
gods and the new.” The way she looked at the king-looked down at him, she was a good hand
higher, though Renly was near as tall as his brother had been-was painful to see.