The very earliest concept for the series saw it being set more than a century after the original, featuring the NCC-1701-7 (not a typo, they really were going to have a number instead of a letter) being crewed by... cadets. When Gene Roddenberry heard about these plans, which were put forward by the studio executives completely independently of him, he rang them up and insisted on taking personal charge of the series.
Roddenberry wasn't actually the first person Paramount turned to when they were looking to create the series. They first approached Harve Bennett, who had replaced Roddenberry as producer of the TOS films starting with Star Trek II: The Wrath of Khan, but he wasn't interested. Then they commissioned a proposal from Greg and Sam Strangis, but Paramount let both go after rejecting their pitch for a "Starfleet Academy" series that they came up with. At this point, Roddenberry's lawyer, Leonard Maizlish, learned that Paramount were shopping around for pitches for a new series, and threatened them with all hell if anyone but Roddenberry was allowed to create the new series, eventually leading to the one we got.
At one point in development, it was proposed to ditch the starship concept altogether and instead increase the power of the transporter to allow the crew to beam from planet to planet every week. The idea didn't last very long, though it did crop up elsewhere.
Interestingly, there is an early model of the Ambassador Class visible in the conference room in a mural of all the ships named Enterprise. The final Ambassador design was very different, but the ship in the mural was never changed. Other examples may be present in the various models of ships found on desks of officers; leftovers of models that were going to be used but never were.
Originally, the crew was supposed to keep the original colors from TOS: Yellow for Tactical/Command, Red for Engineering and Blue for Science/Medical. However, having seen Frakes and Stewart in the red uniforms, they thought they looked better in them and flipped the Tactical and Engineering colors. This is later referenced in the Deep Space Nine episode "Trials and Tribble-ations", when Bashir notices Sisko wearing the 'wrong' colored uniform and has to be reminded of the old ways.
The series was originally going to have a (mostly) original main theme composed by Dennis McCarthy, which you can listen to here. The producers didn't particularly like it, however, and so swapped in Jerry Goldsmith's theme from Star Trek: The Motion Picture, albeit still keeping a good chunk of McCarthy's theme, which plays until the show's title card appears in the final version.
One of the very early ideas tossed around was for the captain to be a hologram. We'd have to wait until Voyager for a similar idea to make it in.
Geordi originally had a Jamaican accent, and Troi was going to be a non-humanoid alien.
Stewart auditioned for TNG three times. Once for Data and twice for Picard. Once bald and once wearing a hairpiece.
Despite portraying a dyed-in-the-wool Frenchman, the French accent was dropped, according to Stewart, due to sounding too silly.
Edward James Olmos was offered the part of Jean-Luc Picard, but declined due to his contractual obligations. Stephen Macht also auditioned for the role, but would later star in "The Circle" and "The Siege", a DS9 two-parter. Yaphet Kotto was also considered.
Marina Sirtis and Denise Crosby were originally going to play Yar and Troi respectively, but switched roles at the last minute.
The writers didn't know what to do with Troi in Season 1, even omitting her from four episodes just to save themselves the trouble. Marina Sirtis has said she was nearly let go after Season 1. She was only kept on because Denise Crosby had already left and Gates McFadden was soon to follow.
Tim "Tuvok" Russ was considered for the role of Geordi LaForge. He came that close to getting it, too.
Among the actors that auditioned for Riker were Jeffrey Combs and Vaughn Armstrong, both of whom became pretty well-known to Trekkies regardless.
Wesley was also, originally, going to be a teenage girl, Lesley Crusher, until Roddenberry decided to cast Wil Wheaton in the part, and gave the character his own middle name.
Wes was also originally intended to be the product of an affair between Picard and Beverly Crusher. This was alluded to in the first two seasons.
Rosalind Chao was a favorite for the role which would eventually became Tasha Yar. Chao was later cast as Keiko O'Brien.
Take another look at that casting letter. Notice a name missing? That's right, Worf was not initially planned for the series. The producers toyed with the idea of a Klingon as a regular crew member in order to parallel the repaired relations between the USA and Russia. The introduction of Worf was actually rather last-minute, which is reflected in cast photos that he is absent from. It also explains why his character didn't really seem to have a permanent post in the first season. One wonders what would have happened if Denise Crosby had not left.
Keye Luke was considered for the part of Dr. Soong (hence the name), but was then in declining health due to age.
Robin Williams was offered the part of the time-traveling "Doctor" Rasmussen in "A Matter of Time", but he was busy working on Hook at the time, so the role was given to Matt Frewer.
Gene Roddenberry originally wanted no aliens from TOS to appear on TNG, and only relented when it was suggested that Worf's presence on the bridge could open up new storytelling possibilities now that the Federation and the Klingons were no longer at war with each other. (The Khitomer Accords, as depicted in Star Trek VI.) An early pitch had the Klingons actually joining the Federation. Another unfilmed episode featured a Romulan crewmember on the Enterprise, suggesting/implying that the Romulans had made peace with the Federation.
The character who eventually became Worf was originally supposed to have been a Marine from the Klingon Empire who simply held a post on a Federation ship.
Beverly was supposed to be the ship's schoolteacher—not doctor. According to David Gerrold, this was changed when he suddenly suggested it during a lunch and the other writers saw the benefits, such as complicating the Ship Tease with Picard and not having to create a separate character to be the doctor.
Data had a remarkably different backstory as a product of alien biomechanics. This idea was probably still in the writers' minds as of "The Naked Now" when Data compared himself to a biological life form in an attempt to explain how he contracted the virus. Peter David took that part and ran with it in his novel Q-Squared, in which an alternate timeline sees Data as a "human-oid": A positronic brain in a human body.
Early ideas for TNG, from episode treatments and scripts that were ultimately not filmed, include a very different origin for the character of Lt. Cmdr. Data. Before the episode "Datalore" as filmed established that Data was an android built by Dr. Soong, his original backstory (according to the unfilmed episode "Terminus" and early versions of "Datalore") revealed that Data was created by an alien species whose technology the Enterprise would encounter but who would remain mostly mysterious and unseen. In some versions of this origin story, they were a civilization of machines. The aliens constructed Data to resemble humans, whom they admired and tried to preserve whenever they encountered them. He was meant to serve as a repository of the memories of a colony of humans who had been wiped out by a mysterious aggressor (eventually developed into the Crystalline Entity).
Also, the Crystalline Entity was initially written as "luring" humans inside and draining them of their neural energy before it was rewritten as a space-dwelling creature who fed by converting mass to energy and stripping entire planets of their ecosystems. In another draft, the Enterprise ran across an alien spacecraft or "object" capable of terraforming planets for human life and creating Data-like androids.
In other variations of the early "Datalore" story concept, the character Lore started as a female android named Minuet. Minuet was written as a gynoid love interest for Data, before they decided to go the Psycho Prototype route with Lore. "Minuet" eventually did show up in the series, but as a holographic love interest for Riker.
The Q Continuum were originally going to be many people with the same face. This portrayal is rather apparent in "Encounter at Farpoint", with each change of costume Q goes through usually resulting in a change in attitude and demeanor. However, by Q's next appearance, this particular idea seems to have been dropped, with Q acting as a single individual, and later episodes (and Star Trek: Voyager) introduced additional members of the Q Continuum.
Elements of an unfilmed TNG story called "The Neutral Zone" (unrelated to the filmed episode of the same name) saw the Enterprise carrying a wheelchair-bound Starfleet dignitary on a critical mission; this made it into the filmed episode "Too Short a Season." The "Neutral Zone" character, Commander Billings, was a Star Fleet security officer who had originally rescued Tasha Yar from her hellish failed colony planet. The Enterprise would have carried Billings on a mission to open trade relations with the Romulan Star Empire. Billings was rewritten as the elderly Admiral Mark Jameson and instead of a Romulan trade mission, the Enterprise carried him to a wartorn planet for a hostage negotiation. Instead of Dr. Crusher performing an experimental procedure which involved transplanting Data's spinal fluid into Billings so he could walk again, Admiral Jameson instead came aboard with the mysterious de-aging compound he'd obtained from another planet. The arms deal angle was similar to Kirk's solution to the Klingons' interference with the social development of another planet in "A Private Little War".
Several unfilmed episodes in the first and second seasons featured the Ferengi, either in person or referenced as a much greater threat to the Federation. The Ferengi were originally supposed to be an aggressive, expansionist empire out there making deals with the Federation's enemies. References in several episodes would have built up their threat, and appearances in other episodes would have depicted them as warriors who were in a state of "cold war" or even "undeclared war" with the Federation, and often competing directly with the Enterprise crew in a manner similar to the Klingons in The Original Series. However, with the Ferengi debuting ridiculously and being later retooled as a species of high-tech merchants who could provide comic relief, the Romulans gradually assumed the role of TNG's main antagonists.
Doctor Selar, played by Suzie Plakson in "The Scitzoid Man", got a great deal of screen time and lines that could just as easily been filled by Pulaski. Writer Tracy Tormé said that he wanted there to be romance between Selar (Vulcan) and Worf (Klingon). When it was time to introduce a new love interest for Worf, they already had a go-to actress. Worf was already stoical as a Vulcan, and K'Ehleyr was a half-blood sassy female, so it's a different interpretation of how "opposites attract".
The Borg were at one point supposed to play a much bigger part in the series than they did. Those Romulan and Federation outposts that were wiped out at the end of the first season were supposed to be foreshadows of a major Borg invasion of the Romulan Empire. A writer's strike wound up forcing the producers to cut and change the story to what was seen in "The Best of Both Worlds". Certainly would have been a darker turn for the series, though.
Maurice Hurley's original plan with the Borg was for season 2 to be a story-arc involving the Federation teaming up with the Romulans and others to fight off the Collective.
The Borg were originally supposed to be an insectoid race who were related to the invading parasites from the first-season episode "Conspiracy". They were later re-imagined as the more budget-friendly cyborgs.
As already stated, other early ideas for TNG included the Neural Parasites from "Conspiracy' being later linked to the (originally insectoid, not cybernetic) Borg Hive. The parasites would have been the Borg vanguard of advanced scouts. The 1st season would have ended with a joint investigative mission into Borg activity by the Romulans and the Federation, chronicled by a trilogy of episodes which would have formally introduced the Borg. Due to the Writer's Strike, these plans were abandoned although elements were present in filmed episodes; however, the neural parasites' connection to the Borg never became canon and was dropped, with the parasites not making another appearance and the Borg reimagined as cybernetic humanoids instead of an insectoid hive.
The writing team tried several times to write a sequel to "The Best of Both Worlds" but nothing went further than the concept phase, because no one could think of another clever way to defeat the Borg. Eventually they gave up and opted to tell a very different Borg story with "I Borg", where the crew rescues a lone drone who eventually gains individuality. It paid off, as the episode proved popular enough to get a follow-up in the "Descent" two-parter.
"All Good Things..." was originally going to feature four time periods, the fourth being the events of "The Best of Both Worlds", with Picard returning as Locutus. This was Braga and Moore's attempt to include the Borg in the series finale, as a follow-up of sorts to the famous two-parter "Best of Both Worlds". Michael Piller felt that four timelines was too confusing, so they chose to ditch it in favor of the other time periods. Braga and Moore feel Star Trek: First Contact was a superior follow-up anyway, so they don't regret cutting the Borg out of the action.
"Yesterday's Enterprise" was originally conceived as two different episodes, one of them titled "Yesterday's Enterprise" and the other unnamed.
In the original script, the Enterprise-C accidentally travels through time; however, it causes no changes in the timeline after being discovered by the Enterprise-D. The entire episode would have centered around Picard having to make a decision to send it back and preserve the timeline, where they would lose a hopeless battle, or risk altering time by keeping them in the present.
The other episode would have involved Sarek and a group of Vulcans revisiting the Guardian of Forever to go back to prehistoric Vulcan. This would have screwed up the timeline and accidentally killed Surak, creating a world where a violent Vulcan race had arisen. They would have eventually discovered and merged with their Romulan offshoots to form a Vulcan-Romulan Empire and would have rampaged across the galaxy, exterminating the Klingons and fighting the Federation (which had formed without them) in a bitter war the Federation was losing. The episode would have even featured the alternate universe Vulcans planning to use the Guardian of Forever to alter Earth's history and prevent the Federation from ever forming, which sounds a lot like Star Trek: First Contact (which even the writers Trent Christopher Ganin and Eric A. Stillwell have pointed out). Sarek, who remains unaffected, is taken into custody on the Enterprise-D where, after a mind meld with Picard, he is allowed to return through the Guardian of Forever to take the place of Surak and preserve the timeline.
Both episode pitches were received well, but Michael Piller suggested merging the ideas together, and Ronald D. Moore ended up changing the Vulcans into Klingons to better explain how the Klingons and the Federation became allies...which, funnily enough, was contradicted a year later in Star Trek VI. The film eventually had to be reconciled with this episode.
Ira Steven Behr and Ronald D. Moore wanted to feature more gruesome deaths for several characters at the end of "Yesterday's Enterprise", including Data being electrocuted and Wesley being graphically decapitated by debris! Riker's on-screen death was said to be even more gruesome, with his throat slit and spurting blood. To make things even worse, the Klingon commanding the enemy fleet would have been Worf! So Worf would have been brutally murdering his friends, essentially, for our viewing pleasure. Moore and Behr were disappointed this wasn't filmed, which they claim was because the producers didn't want to depress audiences, though it was also likely cut due to the graphic nature of the violence.
In the cover page for the first draft of "Yesterday's Enterprise" (which was an unsolicited submission), the writers noted that, in an ideal world, the ship coming out of the rift would be the Enterprise-A, and not the Enterprise-C. However, they followed the instructions in the writers' guidelines which said that no members of The Original Series cast could be used. Rick Berman noted that many years later, when they were in pre-production for Generations, he realized that he should have held back the script and used it for the feature film, because it would have worked much better than the story they ended up using.
The original concept for Sela is that she would have been Tasha and Castillo's daughter, raised by Romulans, and eventually have a HeelFace Turn.
A 1992 Starlog story detailed one episode where, after flying through a cloud of energy, the Enterprise would be taken over by forces led by none other than a still-alive Khan Singh. Khan would claim he had been resurrected and knocked through time by the Genesis Device. After various conflicts, it would be revealed the energy cloud had basically transformed the entire ship into a massive holodeck. The writers wanted to showcase how reliant the crew were on technology and "what happens when it lies to us?" While intrigued, Ricardo Montalban turned the part down, arguing it would mar Khan's great ending in Star Trek II.
Another episode, "Blood and Fire," would have been an AIDS allegory, with Regulan bloodworm infections being one stage in an invasive alien parasites' life cycle. There are many versions of the story of why this particular episode was never filmed. David Gerrold had originally written two (very, very subtly) gay characters into the story, and was later pressured to remove these characters, and the script was rewritten several times (eventually it became a story about zombie infection) before it was dropped, even after the reference to the two gay characters had been removed several drafts ago.
How much better would "The Outcast" have been if the actors playing the sexless J'naii were male instead of female? Jonathan Frakes fought hard to have his love interest for the episode be played by a man, but was ultimately unsuccessful.
Everyone knows about "Blood and Fire", but another episode with similar themes was planned. It involved Wesley Crusher making friends with an alien cadet named "Los", who was from a species who could change sex at will. This would have led them into having a sort of LGBT style relationship, with the episode exploring complex sexual themes. It was pitched by Rene Echevarria, but rejected likely for being too sexual and outside of mainstream audiences comfort zone (which resulted in a gay couple being axed by Echevarria's first episode "The Offspring").
Ronald D. Moore considered bringing Captain Jellico back as the commander of the Enterprise in the Alternate Timeline presented in "Tapestry".
The sixth season episode "Second Chances" revolved around Riker and a copy of himself created 8 years prior. At first, the writers toyed with killing off the original Riker and then having 'Lt. Riker' join the crew, taking Data's position at OPS, while Data became the new first officer. It was a way to introduce a new character (of sorts) while using the same actor. You can see the remnants of this idea in "Chain of Command", when the insubordinate William Riker is relieved of duty, and Data assumes Riker's post.
The original idea for the season 6 cliffhanger was a two-parter titled "All Good Things". When Starfleet orders the sudden decommissioning of the Enterprise, the crew contemplates being split up. While en route to Earth, the Enterprise is attacked, forcing them to flee in the saucer section before the lower half blows up, causing the saucer to crash-land on a planet. If this sounds familiar, it should. Besides re-using the name for the series finale they wrote, the crash sequence was used in Generations, where due to the film budget, was most likely used to greater effect. The reason this concept was ditched was because the producers and Paramount had no desire to shake up the series (especially as the first feature film was already in the works) or to destroy the Enterprise-D (to keep it for the aforementioned film) despite the fact that much of the writing team wanted to destroy the ship and replace it with a sleeker, "cooler" ship. This probably was the motivation for the beefed-up future Enterprise-D in "All Good Things..." and most certainly the motivation behind the Enterprise-E.
Separating the saucer itself was planned to be a much more common tactic, but again effects expenses meant it was only used four times. In addition, halfway through season one it had become painfully obvious that saucer separation was time-consuming and destroyed the pacing, a major issue when it was supposed to happen halfway through dramatic battle sequences.
Originally it was going to be Picard hopping between realities in "Parallels" but Brannon Braga thought Picard's relationships wouldn't change much from reality to reality, and thus would be less jarring, so he decided to make it happen to Worf instead.
The writers considered bringing back Denise Crosby as Tasha in one of the alternate universes, but decided against it, thinking it'd be redundant after "Yesterday's Enterprise".
According to Jeri Taylor, at one point Geordi La Forge was planned to be revealed as the product of alien experimentation on his mother, and an episode was planned to involve said aliens returning to retrieve him. (It's one of many examples of character development that was proposed but rejected on the series.) Even stranger, the concept was almost revived in VOY, with Harry Kim planned to have a very similar backstory; but it, too, was rejected. The idea would eventually be used in a fashion for Sisko in the final season of DS9.
Several attempts were made to introduce the Mirror Universe into TNG. Even Jerome Bixby, the writer of "Mirror, Mirror", submitted a script which would have served as a sequel. It was apparently rejected because it called for guest appearances from TOS. In general, Rick Berman and Michael Piller were disinterested in TNG revisiting the Mirror Universe because they felt the concept was too cheesy and out-of-date. DS9, being staffed by fans of TOS, would eventually re-visit the Mirror Universe to mixed results, with ENT also re-visiting it to surprisingly greater effect (the "In a Mirror, Darkly" two-parter being some of their most popular episodes).
The non-canon novel Dark Mirror released in 1993 (which ended up influencing ENT's foray into the Mirror Universe) and the IDW comic Mirror Broken released in 2017, both explore the Mirror Universe Enterprise-D. Those books are pretty popular, so it's interesting to speculate how TNG would have handled the concept.
The "anti-time" anomaly in "All Good Things..." was originally going to involve Picard and co. having to steal the Enterprise-D from a fleet museum, as an homage to Star Trek III. The sequence would have involved the crew having to go through a museum tour in disguise, with docents getting their names wrong and gawkish tourists annoying them. According to Brannon Braga, it was rejected for being too silly. Ron Moore regretted not being able to keep this in the script, and referenced the concept on Battlestar Galactica (2003).