The death of Legolas and Gimli...did they die?

[Legolas]

then Legolas says to Gimli who complains about the dark message, "Would you have her speak openly to you of your death?"

I believe you're misunderstanding the conversation:

'Then she sent me no message?' said Gimli and bent his head.
'Dark are her words,' said Legolas, 'and little do they mean to those that receive them.'
'That is no comfort,' said Gimli.
'What then?' said Legolas. 'Would you have her speak openly to you of your death?'
'Yes. if she had nought else to say.'

The conversation, at that point, had moved past Galadriel's warning to Legolas. Gimli was disappointed that Galadriel hadn't seen him a message. Legolas is semi-comforting him, saying basically "No news is good news" - or better news, at least, than bad news.

He did not mean Galadriel was speaking of his own death. She warned him about the sea because once he saw the sea, his longing for it would never leave him and he would not be content until he finally set sail across it.