Somewhere in the starting area.
How did they survive the fall?
Same way as all the other origin characters.
What level are we when we come across Karlach?
At least level 1.
Her story is linked to the dodgy Tyr paladin.
She still fell off the spaceship though, having jumped onto it as it passed through Avernus, as she tells you if you question her.