Here's a notion. A controversial Captain (think Ro Laran for example--if she'd stayed with Starfleet and risen to command, there's remain a cloud over her in many eyes, someone like that) is given a prototype new ship. For this reason she's given a very by-the-book first officer, someone she knows and has worked with before, even a friend. But from an old Starfleet family like the Sulus or Stiles. The Chief Engineer is one of the designers of this new ship--let us call her USS Republic. A fairly large percentage of the crew are of a race that recently joined the Federation (within the last few decades) and so the Chief Medical Officer is one of them, as is the Helm Officer. This race (let us call them Gammans, since Alphans/Betazed/Deltans are taken) has a proud warrior tradition, and some of them resent having to obey a non-Gamman Security Chief.
Republic makes contact with a fleet of alien vessels. Let us call the aliens Cygnans (mostly because I just re-read Auden's "Leda and the Swan"). Turns out the Cygnans abandoned all their colonies a thousand years ago, a dozen worlds that now have been colonized in turn, mostly by the Federation but maybe someone else as well. Very private and even a tad paranoid, the Cygnans are none-too-happy to find squatters. But our Captain successfully persuades them to--at least officially--forgive folks for not knowing the Cygnans would return. In fact the Captain makes quite an impression, so much so the Cygnans tend to prefer talking to her in general.
A tenuous agreement is worked out, and another ship--let us call her USS Midway--with a more senior Captain is also sent into the region to help settle things. One mystery in particular is why the Cygnans left, and why they have come back. The most popular theory is that they fled a danger, which has now faded or at least they've found a way of dealing with it--with the implication they aren't telling the Federation about a genuine threat.
Another is the culture shock--Cygnan society being radically different from that of the Federation. Maybe their military have a special place--perhaps they believe that in choosing violence they are condemning their souls to some kind of Hell. But of course this means their warriors feel they have nothing really to lose, while often despising warriors of other cultures as a matter of course.
Just off the top of my head...