A Tholian CO would be doubtful, seeing as how relations between the Assembly and the Federation never seem to be that cosy. I was actually thinking an already well established humanoid Federation species, played by an actor in prosthetics--a new series still needs to be affordable, so there's no point blowing the budget on Captain Jar Jar
As much as I love Vulcans, there emotional detachment and approach could be difficult for an audience to get behind. A Trill would be good, the spots aren't that distracting for none-fans so wouldn't necessarily scare away new viewers (though to make them different from Jadzia, have the character be just a Host, no Symbiont in sight). Though I would love to see a Bolian Captain. We've seen them everywhere and given little snippets about their biology and culture, but not much as been done about them.
But that's just me.
How about a Deltan?
How about a Cardassian, or a Changeling?
How about a Cyborg? (Doesn't have to be a Borg)
How about a Gorn?