Learn English – “Have never done before” vs “never did before”

It depends on exactly when the speaker is talking. Is the speaker talking about something that happened a long time ago, or did the flight just finish? The simple past in "That was a fun flight" and "It was my first flight" makes it sound like the flight is completely over and done and in the past.

Using the present perfect (have never done) sounds wrong if the flight is long in the past and the speaker is remembering it. The reason is that it is a present tense - it is talking about how things are right now! - and it doesn't make sense for the speaker to say I have never done if he's remembering something something he did. But if the flight just finished, then it sounds natural for the speaker to say "I have (at this very moment) never done that before (this time)."

Using the simple past (did) sounds slightly awkward because the speaker is explicitly comparing two times in the past (because we know the flight is in the past, and because of the word "before") and the simple past just puts an event in the unspecified past. You do hear people speak like this sometimes, though.

If the flight is in the long past, the most fluent phrasing, to this US English speaker, would be "I had never done that before." The reason is because the speaker is remembering a past event (the flight) and saying that before that time, he had never done it. If the flight just finished, "I have never done that before" is OK.