Perhaps she offered Legolas the chance to see his father's kingdom become renowned and famous, instead of a backwater forest. Think about it; Legolas is a Sindarin elf. Perhaps there is jealousy towards the High-elves towards journeying to Aman; perhaps Galadriel offered Legolas the chance to see the Sindar become "glorified" (for lack of a better word) like the Noldor. Maybe what he saw in Rivendell and Lothlorien added to this desire. Remember, Legolas was (I think) born much after the departure of the Calaquendi from Beleriand and Middle-earth, so he might feel bitterness about never being given the chance to choose. It's a long shot, I know.
Or maybe there was this horse...
