The origins of the word "compassion" mean "to suffer with".
So, let's get to it. This is more a shell of an idea, a random inspiration if it is of use to anyone. Feel free to further develop it.
The campaign starts off in the early 2290s. The players are assigned to a patrol ship along the Klingon Neutral Zone, with the Organians apparently no longer enforcing the peace. Federation colonies suffer from a series of brutal raids from the Klingon Empire. The campaign begins with a couple of adventures protecting Federation outposts and should expose the characters to the savageness of the Klingon Empire, along with the deceit, broken promises, the way they exploit worlds, etc. The climax of phase one involves protecting a world, but at the cost of the characters' ship (something on the smallish side).
The season two opener involes the explosion of Praxis. While the Khitomer conference gets underway, the characters are reassigned to a vessel assigned to escort relief supplies to the Klingon Homeworld. They must deal with attempts by the Romulans to sabotage this effort - this effort to save the lives of these unworthy barbarians.
The series then continues, with the characters assigned to keep the peace in Klingon space. They have a couple of Klingon representatives aboard and they are assigned to a remote sector, bordering on Romulan Space. As part of the Khitomer Accords, the Federation is helping to preserve the Empire. An Empire which the Romulans see as ripe for the taking. The Klingon Empire is confronted by terrorism, rebelling subject states, former subjects armed by the Romulans, and the occasional Romulan raider. For good measure, many Klingon houses have "gone rogue" and there is a movement to "return to the ways of Kahless" and dismantle the direct rule by the military. Since this takes place in a remote sector, there is also plenty of exploration to be done.
Keeping things interesting is the supposed animosity the characters feel towards the Klingons. If season one is handled right, they shouldn't need much prodding. We want brutal murders by the hundred in season one. Add the fact that the Klingons do not exactly welcome help. But perhaps through Season Two the characters will find some value in the Klingons as they truly learn to work together. Season two has plenty of room for some Klingon PCs. An interesting idea for season one (which I view as a prelude) would be to alternate crews - adventure one the players run Starfleet officers, adventure two they run Klingons, etc.