When King Richard I went to the Holy land during the Third Crusade, he was given the title coeur de lion (French for lion heart). Who gave him that title? I Imagine that it was a French person.
Actually, Richard had acquired that name before he went on the Crusades. Richard and two of his brothers rose up in rebellion against their father, Henry II. They went to France to obtain the support of Louis VII, and it was Louis who actually knighted Richard. This established his initial ties to the French.
When the brothers set out to attack their father, Richard rallied the support of a number of barons from Aquitaine. Eventually, the brothers were defeated and Richard went to his father and begged for forgiveness. His father granted it, but also gave Richard the task of returning to Aquitaine to punish the barons who had fought for him in the rebellion. Many of these barons had very well fortified castles, so this task was not at all easy. It was during this campaign that Richard acquired the name "Lion Heart".
I don't believe there is any record of who exactly coined the phrase, but it was apparently his French adversaries who recognized his courage. I read some sources that suggested it was French minstrels who first used the term to add color to their tales, but no one can be sure.