Expanding my comment above.
For the second part of your question, which is the easier one. Two straight
lines $$a_{1}x+b_{1}y=c_{1}\qquad (1)\qquad\text{ and }a_{2}x+b_{2}y=c_{2}\qquad(2)$$ are parallel if
and only if $a_{1}b_{2}-a_{2}b_{1}=0$, because only then their slope $%
m=-a_{1}/b_{1}=-a_{2}/b_{2}$ is the same (in other words the system of
linear equations (1) and (2) has no solutions, its determinant vanishes).
Let $b_{1}b_{2}\neq 0$. From $(1)$ and $(2)$ we get, respectively, $y=-\frac{
a_{1}}{b_{1}}x+\frac{c_{1}}{b_{1}}$ and $y=-\frac{a_{2}}{b_{2}}x+\frac{c_{2}
}{b_{2}}$. The first line crosses the $y$-axe at $(c_{1}/b_{1},0)$, while the
second, at $(c_{2}/b_{2},0)$. Since the straight line parallel to these two
and equidistant to them crosses the $y$-axe at $\left( \left(
c_{1}/b_{1}+c_{2}/b_{2}\right) /2,0\right) $, and has the same slope $m$,
its equation is $$y=-\frac{a_{1}}{b_{1}}x+\frac{1}{2}\left( \frac{c_{1}}{b_{1}}+\frac{c_{2}}{b_{2}}\right) ,\qquad (3)$$ which is equivalent to $$a_{1}x+b_{1}y-\frac{\ c_{1}b_{2}+c_{2}b_{1}}{2b_{2}}=0 .\qquad (4)$$
Without loss of generality assume that $b_{1}=0$ and $a_{1}\neq 0$. Then $(1)$
becomes $x=c_{1}/a_{1}$ and $(2)$ should be of the form $x=c_{2}/a_{2}$, if
both lines are parallel. The line equidistant to both is given by the
equation $x=\left( c_{1}/a_{1}+c_{2}/a_{2}\right) /2$.
If your equations are $y=c_{1}/b_{1}$ and $y=c_{2}/b_{2}$, the line
equidistant to them is given by $y=\left( c_{1}/b_{1}+c_{2}/b_{2}\right) /2$.
Added. As for the main question I got a different solution, namely, the lines whose equations are
$$\left( a_{1}\sqrt{a_{2}^{2}+b_{2}^{2}}-a_{2}\sqrt{a_{1}^{2}+b_{1}^{2}}%
\right) x+\left( b_{1}\sqrt{a_{2}^{2}+b_{2}^{2}}-b_{2}\sqrt{%
a_{1}^{2}+b_{1}^{2}}\right) y$$
$$=c_{1}\sqrt{a_{2}^{2}+b_{2}^{2}}-c_{2}\sqrt{a_{1}^{2}+b_{1}^{2}}\qquad
\left( 5\right) $$
and
$$\left( a_{1}\sqrt{a_{2}^{2}+b_{2}^{2}}+a_{2}\sqrt{a_{1}^{2}+b_{1}^{2}}%
\right) x+\left( b_{1}\sqrt{a_{2}^{2}+b_{2}^{2}}+b_{2}\sqrt{%
a_{1}^{2}+b_{1}^{2}}\right) y$$
$$=c_{1}\sqrt{a_{2}^{2}+b_{2}^{2}}+c_{2}\sqrt{a_{1}^{2}+b_{1}^{2}}.\qquad
\left( 6\right) $$
The distance $d$ from a point $M(x_{M},y_{M})$ to a straight line $r$ whose
equation is $Ax+By+C=0$ can be derived algebraically as follows:
i) Find the equation of the straight line $s$ passing through $M$ and being
orthogonal to $r$. Call $N$ the intersecting point of $r$ and $s$;
ii) Find the co-ordinates of $N(x_{N},y_{N})$;
iii) Find the distance from $M$ to $N$. This distance is $d$;
after which we get the formula
$$d=\frac{\left\vert Ax_{M}+By_{M}+C\right\vert }{\sqrt{A^{2}+B^{2}}}.\qquad
(\ast )$$
The distances from $M$ to lines $(1)$ and $(2)$ are thus given by
$$d_{i}=\frac{\left\vert a_{i}x_{M}+b_{i}y_{M}-c_{i}\right\vert }{\sqrt{
a_{i}^{2}+b_{i}^{2}}}.\qquad i=1,2$$
The points $P(x,y)$ that are equidistant to lines (1) and (2) define two
lines which are the solutions of $d_{1}=d_{2}$:
$$\frac{\left\vert a_{1}x+b_{1}y-c_{1}\right\vert }{\sqrt{a_{1}^{2}+b_{1}^{2}}}=\frac{\left\vert a_{2}x+b_{2}y-c_{2}\right\vert }{\sqrt{a_{2}^{2}+b_{2}^{2}}}.
\qquad (\ast \ast )$$
Therefore, RHS and LHS should have the same or opposite sign:
$$\frac{a_{1}x+b_{1}y-c_{1}}{\sqrt{a_{1}^{2}+b_{1}^{2}}}=\pm \frac{a_{2}x+b_{2}y-c_{2}}{\sqrt{a_{2}^{2}+b_{2}^{2}}}.\qquad (\ast \ast \ast )$$
Equations $(5)$ and $(6)$ for the two angle bisectors follow.
Example: For $a_{1}=b_{1}=b_{2}=c_{1}=1,a_{2}=c_{2}=2$, we have $x+y=1$ and $2x+y=2$. The equidistant lines are
$$\left( \sqrt{5}-2\sqrt{2}\right) x+\left( \sqrt{5}-\sqrt{2}\right) y=\sqrt{5%
}-2\sqrt{2}$$
and
$$\left( \sqrt{5}+2\sqrt{2}\right) x+\left( \sqrt{5}+\sqrt{2}\right) y=\sqrt{5}+2\sqrt{2}.$$
Graph of $x+y=1$, $2x+y=2$ and angle bisectors.
I'm not sure about the correctness of the webpage linked by @amd (I don't have enough points to add a comment below it).
The author claims: 'However, in these cases, the minimum always occurs on the boundary of G, ...'.
Imagine the line segments defined by $ P_1=(-1,1,0)$, $ P_2=(1,-1,0) $ and $ Q_1=(-1,-1,1) $ and $ Q_2=(1,1,1) $. The shortest distance is not at the boundary of G. It is at s=t=0.5.
I think the correct theory is provided by this PDF: https://www.geometrictools.com/Documentation/DistanceLine3Line3.pdf
There is even an implementation linked inside the PDF: https://www.geometrictools.com/GTE/Mathematics/DistSegmentSegment.h
Best Answer
Since you have two points for each line, we can find the formula for the unique line (assuming the points are distinct). For the first line, defined by $(x_1,y_1)$ and $(x_2,y_2)$, the slope is "rise-over-run", i.e. $\frac {y_2 - y_1} {x_2 - x_1}$, thus any point $x$ and $y$ on this line must have the same slope, so $$\frac {y - y_1} {x - x_1}= \frac {y_2 - y_1} {x_2 - x_1}\implies y=\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x - \left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1+y_1\,.$$For the second line, we get the analogous result:
$$y=\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\,.$$
Now we just have to solve these two equations, since we are looking for the point of intersection where the $x$ and $y$ variables for each line are equivalent, we set the $y's$ equal to each other and arrive at the equation:
$$\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x - \left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1+y_1=\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\,,$$ which we can simplify to $$\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)\right]x= \left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1-y_1 - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\,.$$
Now if $\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)\right]\ne 0$ we can divide to find a specific formula for $x$: $$x=\frac 1 {\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)}\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1-y_1 - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\right]\,.$$ Now, finding $y$ will be easy - we just "back substitute" $x$ into either equation for $y$, say the first one:
$$y=\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)\left (\frac 1 {\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)}\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1-y_1 - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\right] \right) - \left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1+y_1\,.$$
This will always work, unless we have that $\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)\right]=0$. In that case, you either have coincident lines or parallel lines - to determine which, just check the y-intercept of each line (we already know the slopes are equal because of the above condition). If the y-intercepts of each line are equal to each other, then the lines are coincident (so there are infinitely many "points of intersection"). If not, they are parallel (and there are no points of intersection).