Personally ... I think a bit of good old fashioned conquest would be nice. Some possible options would be:
Rekindle the Klingon-Federation War and add some story to the already announced patrols/raids in Pi Canis. Attacking enemy supply lines, escorting an allied freighter convoy, scouting hostile territory ... you could do an entire little campaign that culminates in a big battle for a starbase or some Starfleet Admiral's flagship.
Or: Subjugate some alien species. From the first strike against the other species' forward defenses to the final battle for orbital supremacy right to beaming down and occupying the capital city palace.
A variant of this could be the suppression of Anti-Klingon activities within territories already part of the Empire. Maybe a group of Gorn secessionists backed by someone in the Hegemony's royal court is attempting a coup or wants to incite rebellion in the population. It's up to the player to investigate where these terrorists get their weapons from (Romulans? Undine? Section 31?) and execute their leaders.
Yet another angle of internal conflict would be a conflict between two (or more) noble Houses. This has already been touched in "Bringing down the House", but of course this is a rather important aspect of Klingon culture that can still be expanded. If this is in any way possible, perhaps script the mission in a way that it allows multiple outcomes, depending on the player's choices.
Of course it would also be nice to have some Gorn-, Orion- or Nausicaan-specific missions in the game, but as much as this would enrich the respective species' gameplay I don't think it can be justified to dedicate resources to something limited to a single race. However, perhaps in the future there could be a way to give random missions a unique "touch", such as non-Klingon players not receiving all of their missions from Klingon contacts but ones from their own species, complete with different dialogue to reflect the respective culture.
What I personally don't want to see is more time travel. Just like the mirror universe, time travel is a classic plot device that needs to be used scarcely, lest it looses its distinctiveness.
There definitely should be missions that explore the interactions of the Klingon Empire with the vassal states (Gorn, Orion, Nausiccan, Lethean). They don't need to be specific to the PC's race as any KDF could do them. But a nice twist would be giving the PC an option to either carry out their orders, or to secretly betray J'mpok and aid the resistance instead.
To give an example, maybe the PC is ordered to seek out and destroy a Gorn resistance group. There is a ground conflict that sends the resistance leader escaping in a Gorn ship which the PC has to disable. A Gorn PC could choose to carry out their orders, or to help the Gorn escape by destroying a rival KDF force trying to steal the glory. A Klingon or other PC race would have the same choice, but perhaps a different motive for helping the Gorn escape.
Aside from that, I agree we need more House-vs-House, Undine, and Romulan conflicts. Lots of raiding missions. And more fodder for the war against the Federation. I really like the idea of tying these in with some of the existing Fed missions, to get the other side of the equation.
1. A string of dailies that involve a faction grind for three different houses. Reaching high enough honor within a house can yield decent rewards that will benefit either a Science, Engineer, or Tactical officer depending on which house you choose. However this will leave you with enemies within the other houses. This will open a new form of PVP within the Klingon faction. Fighting members of the opening houses. A way to offer some rewards for dueling other people within the KDF. These duels could be part of the faction grind for defeating members of the opposing houses. And a lot of these fights can happen on newly opened areas of Qo'noS making the Klingon home world more interesting.
2. A series of quests the delve into the history of the Klingons as well as why the Klingons are at war with the Feds again.
3. A quest involving the history of the Bat'leth that opens up a new grind to level your proficiency with this weapon. Ultimately giving a person the title of Sword master. Adding new abilities that only a player who has achieved Sword master could use. and making your Bat'leth abilities more powerful. As well as offering Bat'leths that are green.blue and purple qualities. Offering enhanced dmg buffs, stats. Also have Bat'leths with different skins so the more powerful Bat'leths look more bad ass then other ones. (this could tie into giving Klingons a crafting system. giving a Klingon the ability to become a Bat'leth crafting master.) Create an item that allows us to sharpen our blades offering a minor dmg buff for a certain amount of time. The sharpening stone would be consumed on use. The Bat'leth is such an important part of the Klingon history and has really taken a backseat so far. Perhaps offering a few dailies to level your proficiency that takes you to different parts of Qo'noS to fight various creatures or people. If you are currently leveling your Bat'leth this could open a new Bat'leth specific daily within the grind for house faction I mentioned above. Someone could contact you having heard of your Bat'leth abilities and asks you to take care of "something" for them. The reward could be faction points as well as a new Bat'leth. This idea has a lot of great "Non player leveling" opportunities that STO really needs.
4. Targ breeding. I know it has been mentioned as already a possibility. But structure it similarly to my Bat'leth idea. Not only feeding various Tribbles to create various breads but also have some sort of skill grind to have better control over your animals and allow players who have achieved the title of Targ Master to use them as weapons adding a pet ability bar to the UI with various attacks. You should not be allowed to be both a Targ master and a Bat'leth master at the same time.
5. Have some new achievements that are Klingon specific. Great feats of strength. Very hard to do achievements. What, I am not sure. You guys figure that out. But offer cool rewards for doing so.
6. Add something involving the 2nd Rite of Ascension.
7. Anything Klingons vs Romulen.
8. More KDF VS Borg.
9. Rescuing fellow KDFs from Fed detention.
10. A quest involving Kahless somehow, maybe he could reappear again in the lava caves on the planet of Boreth during a mission that sends you there.
Resolving a conflict between Klingon houses. Listen to their Bards to understand the "truth" behind their conflict.
A mission where you protect the Chancellor as he inspects the frontline, and uncover an Undine conspiracy.
A mission where you have to inspect the activities of a Klingon General that has proven incompetent but for political reasons can't be easily replaced. Find out why his troops remain loyal to him - can you turn them, or do you have to provoke a duel with him to end his command?
A series of mission over the Federation-Klingon war that kinda advances the story of the war itself. Moving deeper into Federation territory, conquering a planett hat the Klingons think of as theirs for a long time. (Maybe revisit the planet where Nog lost his leg - it seems that was one of those "ancient" claims.)
Also a series of missions that involve the Undine threat within Federation ranks. (My idea would be to use the Chancellor-Inspection storyline as base. An Undine among the KDF works together with an Undine in Starfleet to set a trap. In follow-up missions, you follow this lead into Federation space and uncover a major cell of Undine, taking the head of their leader for the Chancellor and the rest for Starfleet to clean up - making the Federation more aware of the threat that is the cause of the war in the first place.)
Do a little more with the Orions, Gorn and Naucassian. Quell a Gorn uprising, help the Naucassian out against a local foe, support the Orion Crime syndicate activities (or end them, because they are dishonorable?)
A series of missions involving the Romulans. House Duras wants to rekindle the relationship, House Martok mistruts them. Solve this conflict. Possibly help a Romulan splinter colony to get free from the Romulans.
Modify the Nemesis system for Champions to work for the Klingons, but rather than a single nemesis it is a rival House; and it can be used when then Romulans are introduced.
As for a specific mission; something that forces a Klingon captain to choose between the good of the Empire and their own personal Honor; with the mission completable either way and with different accolades/trophies and responses for the results.
EDIT: I'll sleep on it and add more later because I'm really tired, lol
The thing the klingon do is conquer, so id like a story or even a general mission type that is repeatable to focus around invading and conquering a star system.
Perhaps you and a small fleet of npc ships have to first attack a group of aliens in a space section with a large space battle, then you move onto another space section that involves disabling their outer defence network, then you move onto their inner perimeter and board one of their orbital control stations. do some damage inside, disable the remainder of their defence grid.
you then beam down to the plant and go on a slaughter and rampage mission before locating their leaders and executing them.
Make it a actual mission type and it can be repeatable just with different aliens each time, and different map layouts like the star clusters.
If it has to be a one off story then do the same thing but against either the breen/federation or romulans and adjust the story to make it more personal.
Perhaps not so much a PVE mission but more a PVE environment, I would like the opportunity to have more hand-to-hand/melee weapon fights. Some sort of Bat'leth arena or "death sports" colosseum would be a nice edition to the Great Hall. Or totally out there, how about some sort of switch in ground pvp for "Melee only" disabling kits and ranged weapons.