Anyone you pick will be dumbed down, its not the show and you need the game to be winnable
ie the Community complained about the D'riedex Defender being too hard for people to beat
I say Tag Team
Since the Iconian 8472 plot has well ran its course and we broke it up in Fluid Dynamics the Iconians turn to someone they don't fully understand and in turn unleash them on all of us.
Think of the Tholians as the Joker
all they want to do like is annex systems and watch the world burn
Hence the Iconians hire them
That's a good idea - would be even better if they actually involved the Iconians, but I suspect that, even if this were the case, their involvment in bringing the Tholians into the 'lets go to war with the Federation' club would be 'behind the scenes'