I guess I'm about half way through the "Klingon War" story arc now. After I finish this, and before I get involved with the next one, I'd like to spend some time doing the "...second star to the right and straight on 'til morning" thing. So, if I'm interested in "five year mission" type stuff, and looking to run into random weird entities, or uncontacted civilizations, which may lead to self contained stories and decisions related to the prime directive, etc. what are my best options in the game?
Head off into the nebulae and vast open regions (ie. those things at the end or side of blocks, like Delta Volanis or the Zenas Expanse). You can pick up a couple daily missions to explore 3 systems & earn dilithium for it.
The missions are a real mix, some use standard races, others are purely randomized. You might get a space investigation mission, or a ground "scan X things" mission, or a "explore these caves / outpost." Oh, and of course, combat missions. It's really the closest thing to exploring strange new worlds in-game.
Keep calm, and continue firing photon torpedoes.
Exploration in STO is fairly crappy, I'm afraid. There are bunch of randomized mini-missions in the exploration clusters, but most of those are just "kill 5/5 ships", "scan 5/5 plants", etc. For gripping stories I'd recommend Foundry missions, when they become playable again.
STO does not offer the type of exploration you're looking for .
If interested , you can repost your OP in the Foundry discussion forum , and ask for recommendations for story themes you'd like to play , such as first contact stories .
For example , look up author Alimac30 in the Foundry .
Yeah, if you're looking for old-school TOS-style adventures, I'm afraid your best bet is to pick up a copy of GURPS Prime Directive and round up some players and a GM. (Come on, you're already being a nerd by playing a Star Trek game - is a tabletop RPG that much worse for your street cred?)
"You're as crazy as the people on Twitter!" - Samuel L. Jackson