I'm not sure if the engine can handle this kind of interactivity with the NPCs, but I'm sure we all remember Vanguard. Vanguard had a very nifty little side game/mini-game for diplomacy. If Cryptic could add a very similar system to STO and integrate it as such that you can reach alternative, less pew pew involved, solutions to missions, they would both please the "too much combat" crowd, and add another layer of depth to the game. As altering current missions to take it into account would probably be a huge pain, it would likely need to either be factored into the generated missions or have its own missions set aside for it at first, and then see it integrated into missions being release going forward.
I know, I know "Cryptic will never do it, they don't care, etc" and you're probably right. But just throwin' this out there. I think a lot of people would get behind this idea if it was done.
First thing I thought of when I read the thread name was Vanguard. It was a pretty fun CCG diplomacy system for a brief while but I wouldn't want to see that done in STO. I'm hoping for more dialogue options that really affect the way the conversation is proceeding and could actually produce a failure in for example a truce negotiation situation where you'd have to escape a fight. Obviously we can't go for strong "good and evil" type of options because every fed captain is a nice(ish *looks at Sisko*) guy/gal. But yeah, Bioware.