After going through my books I can prove my Legolas one as well.
"Nay!" said Theoden. "In the dark hour before dawn I doubted, but we will not part now. I will come with you if that is your counsel."
That is Theoden to Gandalf. There is another instance where Theoden says,
Again, said to Gandalf. Just before saying farewell to Merry and Pippin at Isengard.
You shall visit Fangorn with me, and then I will come with you to see Helm's Deep.
That is Legolas to Gimli.
I haven't been able to confirm my Sam - Frodo guess but I have found a Frodo to Gollum one.