In The Fellowship of the Ring, Galadriel says:
‘We have drunk the cup of parting,’ she said, ‘and the shadows fall between us. But before you go, I have brought in my ship gifts which the Lord and Lady of the Galadhrim now offer you in memory of Lothlorien.’
It seems to me this is out of order. Why not give gifts and then drink the cup of parting, before the shadows grow between them?
Let's look at the preceding lines to your quote, which describe the actual drinking of the cup.
Now Galadriel rose from the grass, and taking a cup from one of her maidens she filled it with white mead and gave it to Celeborn.
‘Now it is time to drink the cup of farewell,’ she said. ‘Drink, Lord of the Galadhrim! And let not your heart be sad, though night must follow noon, and already our evening draweth nigh.’
Then she brought the cup to each of the Company, and bade them drink and farewell.
The Lord of the Rings - Book II Chapter 8 - "Farewell to Lórien"
According to Wayne Hammond and Christina Scull, this passage is a reference to a passage in Beowulf.
Then she brought the cup to each of the Company - In this Galadriel follows ancient customs as portrayed in Beowulf.
The Lord of the Rings: A Reader's Companion
In Beowulf (lines 612-641), Wealhtheow, Queen of the Danes, offers a cup of mead first to her husband Hrothgar, and then to everyone else in the hall.
Here is the passage from Beowulf in Tolkien's own translation:
Wealhtheow went forth, Hrothgar’s queen, mindful of courtesy; with gold adorned she greeted the men in the hall, and then the cup she offered, noble lady, first to the guardian of the East Danes’ realm, and wished him joy at the ale-quaffing and his lieges’ love. He, king victorious, in delight partook of feast and flowing bowl. Then the lady of the Helmings went to and fro to every part of that host, to tried men and young proffering the jewelled vessels, until in due time it chanced that she, ring-laden queen of courteous heart, to Beowulf bore the cup of mead, and hailed the Geatish knight, and gave thanks to God in words of wisdom that her desire was granted to her that she might trust in any man for comfort in their miseries. That cup he then received, grim warrior at Wealhtheow’s hand, and thereupon, his heart being kindled with desire of battle, fair words he said. Thus Beowulf, son of Ecgtheow, spake: ‘This did I purpose when I went up upon the sea and sat me in my sea-boat amid my company of knights, that I wholly would accomplish the desire of your people or would fall among the slain fast in the clutches of the foe. A deed of knightly valour I shall achieve, or else in this mead-hall await my latest day!’ These words well pleased that lady, the proud utterance of the Geat; with gold adorned she went, fair queen of the people, to her seat beside her lord.
Beowulf: A Translation and Commentary - lines 498-521
Note that this cup is not a stirrup-cup given right as everyone is setting out (like we see in Book VI, Chapter 6 "Many Partings": "Now the guests were ready, and they drank the stirrup-cup, and with great praise and friendship they departed").
In both the Wealhtheow scene in Beowulf and the Galadriel scene here in The Lord of the Rings, additional things happen between the passing around of the mead cup and the departure. After Wealhtheow sits down, it is said that feast resumes ("Then again as before were valiant words spoken within the hall, the host was in joyful hour, there was clamour of folk triumphant"). And after the Fellowship drinks, Galadriel sits them all down and hands out gifts. ("But when they had drunk she commanded them to sit again on the grass, and chairs were set for her and for Celeborn.")
