[She smiles when she sees him, dancing up more than walking - nearly all of her movements as as graceful as dance steps, just as nearly all of her words are as sweet as music. Lúthien lived a fairly sheltered life, surrounded by beauty and bringing it with her wherever she went. And she had wandered before, but never to anywhere that looks remotely like here.]

At last, a familiar face. I began to fear I had been lost in a land of only strangers.

[She hesitates, then.]

Or perhaps that might have been preferred.