Also, Bill Campbell made a name for himself playing gangsters, soldiers, in general very tough characters. Trelane was very much a case of Roddenberry casting against type; even then, there are times during that performance where he gets pretty damn dark (probably a lot darker than they would've gotten if they'd gone the logical route and cast Liberace).
As for Koloth, he was playing him as a very slick, devious character, the kind of guy who'd just as soon cut your throat as order a pizza, who we just happen to be catching on a good day.