I would like to see a Co-Faction Mission where another party, Klingon vs Starfleet, can come in and actually effect how the other person beats the mission.

That's a good idea, but how would it be implemented in a way different from goal-oriented PvP maps?

So you choose to start a counter-faction mission. Then what? Do you have to wait in a queue for other faction players to join the mission? Or do you just start, and hope one of them enters? How would the teams be balanced?

I really think if they just added some PvP maps that had more/different objectives, it would be a lot like what you want. Queue up, enter the match, try to scan/beam stuff/rescue or kill NPCs/whatever, while fending off the opposing team.