As for the Terminator...where to even begin (this is from the tvtropes.org page on The Terminator)...
OK, first, OJ Simpson (of all people) was supposed to play the Terminator (the Terminator was envisioned as someone who would blend in with the population). However, either the execs vetoed it because they couldn't see a guy as nice as OJ playing a killer (boy, talk about Harsher in Hindsight) or, according to James Cameron, Cameron himself turned it down because he feared what might happen if the LAPD saw a black man chasing a white woman with murderous intent (and, given what's been in the news recently, he might have had something of a point). Another actor considered was Lance Henriksen, back when the original idea for the Terminator was still in effect; he would play a police detective in the movie itself. Tom Selleck was considered, but turned it down (like he did Raiders of the Lost Ark) because he still had his Magnum, P.I. commitments. Others considered were the following: Michael Douglas, Richard Gere, Harrison Ford, Kevin Kline, Jürgen Prochnow, and Sylvester Stallone (which all would have been interesting; Prochnow would play the actor (Arnold Schwarzenegger) who played the Terminator in a made-for-TV-movie, funnily enough)…
Arnold Schwarzenegger was considered for Kyle Reese--that would not have worked, IMO; Cameron was not going to offer it to him, as he was interviewing Arnold to make his producers happy and, when James Cameron met with him to talk about it, Cameron felt that he was in the presence of a "living machine" and offered the Terminator role to him (rewriting the script to fit Arnold). That worked and it's Arnold's best and scariest role, IMO (to be fair, I also liked him in Kindergarten Cop and True Lies); he's terrifying as the Terminator...
Michael Biehn nearly didn't get the role of Kyle Reese because, when he first auditioned for the role, he was speaking in a Southern accent because he'd auditioned for a stage version of Cat on a Hot Tin Roof and hadn't reverted to his normal accent; however, his agent called and explained what happened, so he got the part after a second reading. Others considered were Mel Gibson, Mickey Rourke, Sting (the singer, not the wrestler of the same name), and Bruce Willis (who's appeared in two of the films mentioned on this thread).
As for Sarah Connor, if you believe tvtropes.org, the following actresses were considered for the role of Sarah Connor: Rosanna Arquette, Kim Basinger, Glenn Close, Jamie Lee Curtis, Geena Davis, Mia Farrow, Carrie Fisher, Jodie Foster, Teri Garr, Jennifer Grey, Melanie Griffith, Goldie Hawn, Anjelica Huston, Amy Irving, Diane Keaton, Margot Kidder, Diane Lane, Jessica Lange, Madonna, Liza Minnelli, Michelle Pfeiffer, Gilda Radner, Miranda Richardson, Meg Ryan, Susan Sarandon, Jane Seymour, Brooke Shields, Sissy Spacek, Sharon Stone and Sigourney Weaver were all considered for the role of Sarah Connor. It was offered to Daryl Hannah (who turned it down in favor of Splash), Kate Capshaw (who turned it down in favor of Indiana Jones and the Temple of Doom), Kathleen Turner (who turned it down to do Romancing the Stone, which she starred in with Michael Douglas, who was considered for the Terminator role), Julia Louis Dreyfus (which would have been interesting--she turned it down for Saturday Night Live), and Debra Winger (who turned it down before filming began)…
One idea was to end the movie with the tanker explosion; James Cameron wanted it to end on the chase through the factory and in Kyle's death, and won out...