In my game Sarah was killed, and she was my companion almost from the beginning. In my understanding, the one who gets killed is the one that is my companion when the mission A High Price To Pay begins. But someone else can probably give a more exact explanation.
I liked Sarah quite much, but I wasn't romantic with her. After she was killed, I was disappointed with the game for some time. I have never felt Andreja interesting because she feels distant and suspicious, and because Sarah is prettier.