How can we show that $\mathrm{Re}(z + \sqrt{1+z^2}) \ge 0$ for all complex $z$?

Consider the numbers $$ w_1 = z + \sqrt{1+z^2} \, , \, w_2 = z - \sqrt{1+z^2} \, . $$ Then $$ \tag{1} w_1 - w_2 = 2 \sqrt{1+z^2} \implies \operatorname{Re}{w_1} \ge \operatorname{Re}{w_2} $$ from the choice of the square root, and $$ \tag{2} w_1 w_2 = -1 \implies w_1 = - \frac{\overline{w_2}}{|w_2^2|} \implies \operatorname{Re}w_1 = - \frac{\operatorname{Re}w_2}{|w_2^2|}\, . $$ If we assume that $\operatorname{Re}w_1 < 0$ then $$ \operatorname{Re}w_1 < 0 \underset{(1)}{\implies} \operatorname{Re}w_2 < 0 \underset{(2)}{\implies} \operatorname{Re}w_1 > 0 $$ gives a contradiction, so that $\operatorname{Re} w_1 \ge 0$ must hold (and $\operatorname{Re}w_2 \le 0$).

Alternative (but equivalent) approach: $w = z + \sqrt{1+z^2}$ satisfies $$ w + \frac 1w = 2 \sqrt{1+z^2} \, . $$ It follows that $$ 0 \le \operatorname{Re}\left( w + \frac 1w \right) = \operatorname{Re} w \cdot \left( 1 + \frac 1{|w|^2}\right) $$ and therefore $\operatorname{Re}w \ge 0$.

One can also see that $\operatorname{Re}w = 0$ if and only if $\operatorname{Re}(\sqrt{1+z^2}) = 0$, and that is exactly for numbers of the form $z = ia$ with $a \in \Bbb R$, $|a| \ge 1$.