Honestly, although I like exploration stories and hope to see one, the fact is that not as much of Star Trek is about exploration as we tend to think. Just to look at TOS's first season:
"Where No Man Has Gone Before": Exploration (gone horribly wrong)
"The Corbomite Maneuver": Exploration/first contact
"Mudd's Women": Chasing a criminal, repairing the ship
"The Enemy Within": Transporter malfunction (with a backdrop of exploration)
"The Man Trap": Colony resupply, killer monster
"The Naked Time": Disease with exploration backdrop
"Charlie X": Dangerous passenger
"Balance of Terror": Fighting off invading enemy
"What Are Little Girls Made Of?": Rescue of lost explorer, android threat
"Dagger of the Mind": Routine penal-colony visit exposes corrupt administrator
"Miri": Exploration/disease
"The Conscience of the King": Investigation of war criminal, murder mystery
"The Galileo Seven": Exploration/rescue
"Court Martial": Court martial
"The Menagerie": Another court martial (well, preliminary hearing)
"Shore Leave": Shore leave (gone horribly wrong)
"The Squire of Gothos": Routine mission interrupted by nasty alien
"Arena": Fighting off invading enemy
"The Alternative Factor": Investigating dangerous cosmic anomaly
"Tomorrow is Yesterday": Accidental time travel
"The Return of the Archons": Exploration, but in search of lost ship
"A Taste of Armageddon": Diplomatic contact (gone horribly wrong)
"Space Seed": Stumbling across mysterious ship
"This Side of Paradise": Investigating incommunicado colony
"The Devil in the Dark": Investigating deaths at mining colony
"Errand of Mercy": War story
"Operation -- Annihilate!": Fighting monsters
That's just a limited sample, of course, but Trek episodes that are really about exploration and first contact are few and far between. And many of those that start out with exploration missions make them just an incidental backdrop to a story about something else. There have always been plenty of episodes about fighting monsters and enemy aliens and conquerors and lunatic killers and the like.