I think the original "Terminator" was more like the predestination paradox depicted in TNG's "Time's Arrow," not "ST: First Contact."
The events in the past were caused by the events in the future, which were caused by the events in the past (aka, chicken-and-egg).
In the first movie, nobody was CHANGING the past; both the Terminator and Reese were fulfilling their destinies. Maybe they thought they could change the past from watching too many "Star Trek" re-runs, but they actually couldn't change anything.
As a stand-alone movie, "The Terminator" is a perfect depiction of a causality loop.
However, with "T2," the concept of free will is introduced, where the characters start to believe that, with knowledge of the future, they can actually CHANGE or PREVENT the future from happening. That shoots the whole causality loop from the first movie to hell.
Then in "T3," the concept of "Fate" is introduced, where even with knowledge of the future, and the characters trying to change the future, time (or God, or the Fates) corrects itself, and Judgment Day becomes inevitable, even if delayed.
At the same time, the two Terminators in "T3" are on contradictory missions. The T-X has come back in time to kill her future enemies while they are still teenagers. She is clearly CHANGING her own past. But at the same time, the T-800 follows her back, and seems to know her from his own future, but his mission is to allow Judgment Day to happen, and help John and Kate survive, exactly as he already knows it will happen. In other words, the T-800 is there to fulfill his destiny, and keep everything exactly the same as he remembers, while the T-X is trying -- and succeeding -- to change her own past.
So it's the original "Terminator" that is the only movie that makes sense on its own, as a self-contained causality loop. It's the sequels that go off the rails, completely negating everything established about time travel in the first movie.
Then throw in "The Sarah Connor Chronicles," which introduces the concepts of both FORWARD time travel (vanishing from the timeline, then reappearing years later), plus the concept of alternate timelines, where every time someone goes to the past and changes stuff, their future is gone and is replaced with an alternate future.
So yes, using "TSCC" logic, then Reese could not have followed the T-800 back into the past in the original "Terminator" movie, since he would be in a different alternate future than the one the Terminator was creating. But that is a comment on the sequels and the TV series, not the original movie's logic.