I bet that the Westernmost place that Legolas had travelled was Rivendell, unless he was born before Oropher's arrival in Greenwood.
My pick goes to a Dwarf. There are some mentioned in Bilbo's party, and Gimli passed from Lorien as a memmber of the Fellowship. Does he has any mentioned cousin? If yes, my guess would go there.
|