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.
But in retrospect, looking back on the characters after having seen them in other works: 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."
And maybe Michael Strong as Roger Korby was an odd choice, since he usually seemed to play heavies in '60s shows, and maybe that gave away the game too soon.
The most bizarre casting choice has got to be celebrity lawyer Melvin Belli as Gorgon, but I'm not sure I'd call that an interesting choice, just a painfully bad one.