^ Or a combination of this.
Personally (and I've written this elsewhere) I would love to see the movie start off first with stuff back in ancient Egypt, showing us Apocalypse as a youth and then him finding alien technology. He creates his pyramids (in Giza) to hide the ship.
We then see a scene from 1976 where we see Raven give Wolverine's body to Sinister. We see that she did this in order to get something that has to do with saving/protecting mutants. Maybe the location of Destiny!
We then see a Danger Room sequence with Jean and Scott, and possibly a Quicksilver, already recruited. Have Beast running it and have it explained generally how Beast created the Danger Room and created Scott's glasses. Show each of their personalities. Scott's natural leadership, Jean's uncertainty (possibly) and maybe Quicksilver's overconfidence.
We then see Xavier using Cerebro, and see him find another mutant (Nightcrawler) in Germany (at the circus). We see that he is bald (pay McAvoy extra). They go to recruit him.
We then see Gambit in Cairo and a scene where a young Ororo tries to steal from him. Doesn't work out as she expects, but Gambit uses his powers to Ororo's astonishment.
Back with Xavier and the X-Men we see them visit the circus. Something happens, young Nightcrawler exposes his powers, he decides to go with Xavier. We even get to see (from Margali's point of view) how Kurt came to be raised by her (Mystique left him).
We then see Gambit (in uniform) entering the pyramid. Storm follows him in. Her presence (which obviously didn't happen in the OT for whatever reason) leads to a slumbering Apocalypse being awoken. Gambit tries to save Ororo and escape and causes a cave-in, killing a Horseman (Death) but trapping Ororo.
Back on the Blackbird we see Xavier (and maybe Jean) react to Apocalypse's energy. They head to Cairo.
Back with Ororo, she freaks out and her powers cause lightning to blast the pyramid. The X-Men appear, a short battle with the remaining Horsemen, they have to escape since Ororo is hurt. Gambit goes with them.
We see Apocalypse visiting Sinister (Sinister is obviously subserviant - they must have met in the past) and him needing a new Horseman Death. Wolverine's body is presented and we see the start of him being turned into a Horseman.
We then see Mystique and her Brotherhood (Toad, Spyke, Ink, and maybe a better done Blob) attacking a government facility. They get to the point where they free Destiny, but they are trapped. Possibly Ink or Spyke are killed. Magneto shows up out of knowhere to save them.
Back at the X-Mansion we see Ororo being tended to and Gambit by her side. They discuss this whole omnipotent being they met and question Gambit. He provides just a bit of insight (would Xavier use his powers to uncover the truth?, could Gambit prevent it?).
Then at Magneto's lair (within a mountain) he reveals to Raven some truths about the past, as does she. She gets into the whole "you left me" and "you tried to kill me" stuff. Erik explains how he is going to create a free society for mutants. Mystique doesn't comit to anything. Maybe Destiny convinces Raven that Xavier needs to be told about how she gave Wolverine to Sinister (she sees what he will become). Erik goes with her (and Destiny) to visit Charles (Raven to explain, Erik to invite them to come with him).
We then get to see the whole Wolverine reveal. He is the Horseman Death.
Back at Xavier's Mystique, Erik and Destiny show up and they get into what they know about Wolverine and Sinister, and the coming Apocalypse. Magneto reveals to Quicksilver that "I am your father". Quicksilver goes, but no one else.
Raven and Xavier go through some stuff. They agree to work together for now in order to undo what she did (Wolverine) and stop Apocalypse. Although Kurt isn't informed that Mystique is his mommy, maybe Xavier and she get into it a bit. She convinces Charles not to tell...
Apocalypse and his forces attack somewhere, and the X-Men and Mystique go to stop them. We have a good battle, a few dead Horsemen, Xavier getting through to Wolverine, who turns on his "master", allowing an all out assault to work. Would need some good combos between the X-Men. With Apocalypse defeated the X-Men leave and Mystique goes her own way.
We then get to see Erik, along with a number of followers (maybe around 30 or so) at his base of operations. We see him use his powers to rip the mountain from the Earth and propel it into space. He creates Avalon.
Back at the X-Mansion we get a happy, feel good scene showing the four X-kids and maybe something along the lines of how Gambit is not there, but he's coming back (maybe a conversation between him and Storm). The movie ends with some discussion about Erik and how the governments of the world are going to react, and maybe some other stuff. But we get to see all four of the X-Kids happy and healthy, etc.
After credits scene: We see Sinister back in Cairo putting the remnants of Apocalypse into the regeneration chanber. Gambit shows up and gives to Sinister whatever it was that he was originially sent to obtain. This way the GA sees that Gambit was working for Sinister and that Apocalypse is a threat that can come back in the future. We also see that Sinister is a future threat that could pop back up in either a future Gambit flick, or in another X-Men movie...
