The problem for me is, I've been a Trek fan since I was five years old, so Trek was the first place I ever saw most of its actors. So my image of those actors is defined by their Trek characters, and thus it's hard for me to be surprised by any of their casting. . .
I'm sort of in the same predicament with the question. I was 15 when TOS first aired, and Trek was one of the shows airing when I had only just started to pay attention to actors' names. I'd seen Shatner several times before in Twilight Zone, Outer Limits, and even Man from UNCLE, but he didn't register with me as anyone notable until Star Trek. Skip Homeier however, I first noticed on the Outer Limits because I liked the scary makeup.
. . .I've often found it amusing to see Charles Napier as the quintessential space hippie Adam in "The Way to Eden," since he went on to make a career playing stern, tough authority figures, basically becoming the quintessential "Herbert."
I just looked at Napier's IMDB page. Star Trek is only his fifth film/tv role, his first appearance anywhere was a year earlier in 1968 as an uncredited Police Officer on Mannix