Right after Pulp Fiction came out, they were all the rage. I especially remember Go with Katie Holmes. Loved that one and sorry it didn’t hit with people. Another was a foreign film-- I don’t remember if it came before or after Pulp Fiction-- named Run, Lola, Run. It was non-linear but not quite the same way as PF and Go. It’s timeline is a bit more like Groundhogs Day.
The structure of Pulp Fiction is definitely inspired by The Killing, but Reservoir Dogs is actually more of a direct homage, and also has a non-linear structure (the inciting incident of the heist is never shown, and then several characters are introduced in flashback).
A lot of films have a non-linear structure in terms of bookending and extensive narrative flashback, but what I find particularly difficult to do well are films told in reverse; in addition to @YamatoTwinkie’s reference to Memento, there is Gaspar Noé’s Irreversible (where it is something of a gimmick), and my favorite, Eternal Sunshine of the Spotless Mind written by Charlie Kaufman and directed by Micheal Gondry, where the film is literally being told in reverse as the protagonist is re-experiencing memories as they are being erased, bookended by his pre- and post-erasure condition.
Slaughterhouse-Five (based on Kurt Vonnegut’s novel of the same name) is told out of chronological order, as it’s the story of Billy Pilgrim, a man who is “unstuck in time” – its scenes go back and forth between Billy’s experiences as a soldier in World War II, his postwar life as a family man and optometrist, and his abduction by aliens.
Pretty much all of Nolan’s movies, outside of the Batman trilogy mess around with time in some way. For example in The Prestige the movie is told through the device of one character reading another character’s diary in which he’s reading the original character’s diary.
It has been some years since I’ve seen it but Passage to Marseille (1944) is told in the style of flashback within another flashback within another until the whole story snaps back to the ‘now’ of the opening scene.
Momento is still linear even though it’s backwards.
Rashomon needs to be mentioned.
(500) Days of Summer bounces around a lot. But that’s a terrible movie with an insufferable protagonist.
So let’s go† with Brick. It’s not Pull Fiction level nonlinear, but it uses a fairly common method. It begins with a brief but impactful scene in the middle of the story, then goes back to the beginning. When the movie meets up with the opening scene, it continues from there.
Within the individual scene/segment, its still plays out normally. There are also the black & white segments interspersed that are in regular chronological order. The timeline looks more like a sawtooth than something that could be described as “linear”.
Citizen Kane (1941) – Which set a much-copied standard for flashback-filled dramas.
The Locket (1946) – Like Passage to Marseilles, it features flashbacks within flashbacks within flashbacks.
Last Year at Marienbad (1967) – Screenwriter Alain Robbe-Grillet also wrote and directed a number of films, many of which are nonlinear (and boring).
Two for the Road (1967) – In which Audrey Hepburn gets to wear high fashion from top designers in multiple time periods.
Happy End (1967) – In which the narrative is told in reverse from the protagonist’s execution to his birth.
One Deadly Summer (1983) – In which different characters take turns narrating events of the story.
Re: Reservoir Dogs – “Hong Kong film director Ringo Lam saw the Indian film Gaddaar (Vinod Khanna), years ago. He took the basic idea of the plot and made “City On Fire”. Quentin Tarantino’ saw that film and was inspired to make Reservoir Dogs. Sanjay Gupta decided to make his own version with Kaante.” [from IMDB City on Fire Trivia]
Gambit. The movie shows a heist, then goes back to show what really happened.
Annie Hall. When it was first broadcast, ABC had extra operators on duty to field complaints about the use of the word “asshole.” But the biggest complaint they fielded was that the (non-linear) film was being shown out of order.