Is eqnarray really obsolete?

The output of eqnarray is wrong anyway and there's little to do about it. Consider also that it doesn't work with cross-references if hyperref or cleveref are involved.

No, there's no reason for using it.

The first example can be dealt with using array:

\documentclass{article}

\usepackage{amsmath,array}

\begin{document}

\begin{equation*}
\renewcommand{\arraystretch}{1.5}
\begin{array}{@{} r @{} >{{}} c <{{}} @{} l @{} }
2^n
 & =                   & \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n \text{ times}}\\
 & \overset{n>3}{=}    & 2 \cdot 2 \cdot 2 \cdot 2 \cdot \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n - 4 \text{ times}}\\
 & =                   & 16 \cdot \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n - 4 \text{ times}}\\
 & <                   & 24 \cdot \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n - 4 \text{ times}}\\
 & =                   & 1 \cdot 2 \cdot 3 \cdot 4 \cdot \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n - 4 \text{ times}}\\
 & \overset{n>3}{\leq} & 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot \ldots \cdot n\\
 & =                   & n!
\end{array}
\end{equation*}

A better proof, by induction, is
\begin{alignat*}{2}
2^4     &= 16 < 4! = 24  \\
2^{n+1} &= 2\cdot 2^n    &\quad&\text{for $n>3$} \\
        &< 2\cdot n!     &\quad&\text{induction hypothesis}\\
        &< (n+1)\cdot n! \\
        &= (n+1)!
\end{alignat*}
\end{document}

The second example is even easier: use a good alignment point:

\documentclass{article}

\usepackage{amsmath}

\begin{document}

\begin{align*}
\sigma =[ &x_1/t_1,x_2/t_2,\\
          & x_3/t_3,x_4/t_4]
\end{align*}

\end{document}

More lines can be accommodated:

\documentclass{article}

\usepackage{amsmath}

\begin{document}

\begin{align*}
\sigma = [ &x_1/t_1,x_2/t_2, \\
           & x_3/t_3,x_4/t_4] \\
\tau   = [ &y_1/t_1] \\
\psi   = [ &x_1/t_1,x_2/t_2,\\
           & x_3/t_3,x_4/t_4]
\end{align*}

\end{document}

Use \mathclap:

\documentclass{article}    
\usepackage{mathtools}    
\begin{document}
\begingroup 
\advance\thickmuskip by 5mu  % 5mu = 5/18 em
\begin{align*}
    2^n &=                      \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n \text{ 
    times}}\\
    & \stackrel{\mathclap{n > 3}}{=}    2 \cdot 2 \cdot 2 \cdot 2 \cdot \underbrace{2 
    \cdot 2 \cdot 
    \ldots \cdot 2}_{n - 4 \text{ times}}\\
    & =                      16 \cdot \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n - 4 
    \text{ times}}\\
    & <                      24 \cdot \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n - 4 
    \text{ times}}\\
    & =                      1 \cdot 2 \cdot 3 \cdot 4 \cdot \underbrace{2 \cdot 2 \cdot 
    \ldots \cdot 2}_{n - 4 \text{ times}}\\
    & \stackrel{\mathclap{n > 3}}{\leq} 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot \ldots 
    \cdot n\\
    & =                      n!
\end{align*}
\endgroup

\end{document}