I started posting this in another thread simply as I've become tired of seeing "If you want that feature play Fed" or "that isnt what Klingons do." I do not agree with that assessment.
The Klingon Empire survives by expansion and conquest. This can not be done with out exploration. And, with exploration comes the need for Diplomacy and First Contact. Below are a few examples.
Mission Type: First Contact (Primitive Race)
--Arrive in System, Objective: Scan the Planet--
"Captain, Scans have revealed that this planet is very rich in duratanium and dilithium. We have been ordered to conquer it in the name of the Empire."
--Beam Down and "survey"
"Captain, our scouts have made contact with a indigenous race on this planet. They are inferior to us technologically, but could make worthy additions to the Empire. They may interfere with mining operations in the area."
1) Exterminate the indigenous race
Mission Updates, Eliminate 5 Groups of Indigenous Lifeforms; Destroy 5 Dwellings
2) Talk to Tribal Elders - "Diplomacy"
Mission Updates, Talk to Tribal Elders, options either lead to Exterminate the Indigenous Lifeforms OR Engage Elder in Ritual Combat. Ritual Combat has a chance of awarding one of the locals as a new BO.
Ritual Combat: The Captain engages in Single Combat against the Chief of the Tribe using Melee Weapons only. These could be "special" random weapons. Combat could come in several waves before getting to the final boss, the chief.
3) Collect Samples
Mission Updates, Collect 6x Metallurgical Samples to determine if orbital scans were correct. Has a chance of spawning Indigenous Lifeform groups to defend the sample locations.
Result: First (or Last) Contact has been made with a new race. Blood has been spilled for the Empire.
Mission Type: First Contact (Advanced Race)
--Arrive in System, Objective: Scan Unknown Object--
"Captain, Sensors are picking up a high concentration of an exotic alloy with useful properties. We should close for more detailed scans."
--Press F to Restore Power, or play "restore power minigame"--
"Scans indicate that this probe suffered severe damage from [Energy Type] Based Weapons. We should be able to restore power and scan its memory core to locate the probes' origin."
--Defeat Attacking Squadron--
"Captain! The probe is broadcasting a distress call. It originated from the Xth planet in the system. The [insert new race here] are being blockaded by the [insert baddies here]. This probe was sent to High Council to request our protection."
--Defeat X enemy squadrons-- (no more than 3)
"Captain, the enemy flagship is moving to engage us!"
--Defeat Lead Squadron--
"Captain, we are being hailed by the leader of the [insert race name here."
1) Inform the leader that they are now Subjects of the Empire; reward: new bridge officer
2) Demand samples of the metal, in exchange you will spare there pitiful planet; reward: new random resistance console.
Result: First Contact has been made with a new race. The Empire has gained new technology and/or territory. Blood has been spilled for the Empire.
Mission Type: Exploration (Fauna Survey)
--Defeat Federation Survey Vessel--
"Captain, we have been ordered to conduct a survey of the Fauna on this planet, however, I am detecting Starfleet p'taqh already in orbit. We must eliminate them before we can beam down."
"The System is clear, and your targ has been prepared for transport. Good hunting, Captain."
--Kill X critters of various types and collect samples-- There are no BO's present on the surface, however the Captain has his or her Pet Targ controllable in the same manner as normal BO's
Mission Reward: "Stuffed Animal Head" to mount in Captain's ready room.
Result: A planetary surface has been explored for the Empire. And blood has been spilled for your Targ, and the Empire.