Keep in mind that "always" in front of a verb requires the verb's -ing form.

As GeneBurnsUSA said, it is also a matter of timing.

"By the time" usually implies that the action in the second half of the sentence has already started in the past. Here are a few natural-sounding examples:
"By the time the ambulance arrived, it was too late (he was dead)"
"By the time we arrived, the music had stopped"
"By the time I woke up, she was already cooking"

In your specific example:
"When we arrived, the film was starting" would sound best, if the film is indeed starting at the moment you enter the cinema.
"By the time we arrived, the film had started" would sound best, if the film started before you entered the cinema.

"By the time we arrived, the film was already starting" would indeed also sound OK, but do note the difference - "already" ;-)