Obviously Shatner and Nimoy, but also the lovable John Fiedler (of 12 Angry Men fame, as the possessed Mr. Hengist in TOS's "Wolf in the Fold" and a cardiologist in Columbo) and the fantastic Theodore Bikel (as the murderer in Columbo's "Bye-Bye Sky High I.Q. Murder Case", and as Worf's adoptive dad in TNG's "Family"). Ed Begley Jr, whose father was in 12 Angry Men, is in ST:VOY as Henry Starling, and in Columbo's "How to Dial a Murder" as Officer Stein. Laurence Luckinbill is Sybok (STrek V) and the victim in Columbo's "Make Me a Perfect Murder". Michael Strong: Columbo's "are you a witness to what he just did?" scene, and TOS's Dr Korby.
There are metric tons of links with minor characters, for example James Greene in the Columbo classic "Columbo Goes to the Guillotine" is also in TNG and DS9.
Dozens more are discussed here: http://pub10.bravenet.com/forum/static/show.php?usernum=8065...
There are other amusing non-Star Trek but sci-fi-related coincidences too, like Robert Culp (IMO the best Columbo villain, a first-rate actor) voicing Dr. Breen in Half-Life 2.
Obviously you could do this with absolutely any TV show, since there aren't that many actors in America, but this is a fun exercise and fans of both shows have a lot to be happy about. And if you're a fan of one, and start watching the other (I started with Columbo, possibly unlike most people here), try spotting common actors as a fun exercise.