Let $E$ be a finite-dimensional vector-space on $\mathbb C$. Take any $a$, $b$ endomorphisms of $E$.
Show there exist a basis $(e_1, ... e_n)$ and a permutation $\sigma$ such that the matrix of $a$ in $(e_1, ... e_n)$ and the matrix of $b$ in $(e_{\sigma(1)}, ... ,e_{\sigma(n)})$ are upper-triangular.
Here some thoughts.
Induction does not seem appropriate.
Let $(a_1, ... a_n)$ be a triangular basis for $a$ and $(b_1, ... b_n)$ be a triangular basis for $b$.
The first step is easy: take $a_1$ as $e_1$ which is an eigen-vector of $a$ and $b_1$ an eigen-vector of $b$.
One can choose $i$ such that $b_1 = e_i$ chossing $i \neq 1$ minimal.
Then $Vect(e_1, a_2, ... , a_{i-1}, e_i) \cap Vect(b_2,...b_n) \neq$ $\{0_E\}$
So let $x$ in this intersection.
$x$ can be colinear to $e_1$
...
As in the OP, let ${\cal A}=(a_1,a_2,\ldots,a_n)$ be a triangular basis for $a$ and let ${\cal B}=(b_1,b_2,\ldots,b_n)$ be a triangular basis for $b$. We use a one-sided variant of the classical Gaussian elimination procedure (I do not know if it has a name already).
Operations on columns of a matrix correspond to right multiplications by certains matrices. The fundamental fact is the following : if $(r_{ij})$ is a $n\times n$ matrix and $M$ is a $n\times n$ matrix written in columns $M=[M_1|M_2|\ldots|M_n]$,
$$ [M_1|M_2|\ldots|M_n]\times (r_{ij})=\Bigg[ \sum_{i=1}^n r_{i1}M_i \Bigg| \sum_{i=1}^n r_{i2}M_i \Bigg| \ldots \Bigg| \sum_{i=1}^n r_{n1}M_i \Bigg] \tag{2} $$
It follows from (2) that two bases are upper triangular in one another iff there is a lower (not upper!) triangular right multiplication matrix relating them. In particular, there is a lower (not upper!) triangular $n\times n$ matrix $A$ such that
$$ [aa_1|aa_2|\ldots|aa_n]=[a_1|a_2|\ldots|a_n]A \tag{3} $$
It also follows from (2) that if $P_{\sigma}$ is the permutation matrix whose columns are $u_{\sigma(1)},u_{\sigma(2)}, \ldots u_{\sigma(n)}$ for some $\sigma \in {\mathfrak S}_n$, (where $(u_1,\ldots,u_n)$ is the canonical basis of ${\mathbb C}^n$)
$$ [M_1|M_2|\ldots|M_n] P_{\sigma}=\Big[ M_{\sigma(1)}\Big| M_{\sigma(2)}\Big| \ldots\Big| M_{\sigma(n)} \Big] \tag{4} $$
With (2) in mind, let $C$ be the unique invertible matrix satisfying
$$ [a_1|a_2|\ldots|a_n]=[b_1|b_2|\ldots|b_n]C \tag{5} $$
We now reduce $C$ to a sort of echelon form :
Since $C$ is invertible, there is some index $j_1$ such that $c_{1j_1}\neq 0$. Take the largest such $j_1$. Then, using column operations (multiply the $j_1$-th column by $\frac{1}{c_{i_11}}$, then use that column as a pivot to make all other coeffs in the first row to be zero. Note that the coeffs to the right of $c_{1j_1}$ are zero already and do not need to be changed), there is a lower triangular matrix $L_1$ (in fact, a product of a diagonal matrix and some transvections) such that the first row of $CL_1$ is $u_{j_1}$.
Since $CL_1$ is invertible, there is some index $j_2$ such that the $(2,j_2)$ cofficient of $CL_1$ is nonzero. By construction $j_2\neq j_1$. Take the largest such $j_2$. Then, using row operations, there is a lower triangular matrix $L_2$ (in fact, a product of a diagonal matrix and some transvections) such that the first two rows of $CL_1L_2$ are $u_{j_1},u_{j_2}$.
Continuing like this, we eventually obtain a lower triangular, invertible matrix $L$ such that $CL=P_{\sigma^{-1}}$ for some $\sigma \in {\mathfrak S}_n$. Next, define a new basis $(e_1,\ldots,e_n)$ by
$$ \begin{array}{lcl} [ e_1 | e_2 | \ldots | e_n ] &=& [ a_1 | a_2 | \ldots | a_n]L \\ &=& [b_1|b_2|\ldots b_n]CL \textrm{ by } (5) \\ &=& [b_1|b_2|\ldots b_n]P_{\sigma^{-1}} \\ &=& [b_{\sigma^{-1}(1)}|b_{\sigma^{-1}(2)}| \ldots |b_{\sigma^{-1}(n)}] \textrm{ by } (4). \\ \end{array}\tag{6} $$
Applying $a$ on both sides of the first inequality in (6), we have
$$ \begin{array}{lcl} [ ae_1 | ae_2 | \ldots | ae_n ] &=& [ aa_1 | aa_2 | \ldots | aa_n]L \\ &=& [a_1|a_2|\ldots a_n]AL \\ &=& [e_1|e_2|\ldots e_n]L^{-1}AL \\ \end{array}\tag{7} $$ The matrix $L^{-1}AL$ is lower triangular since it is a product of lower triangular matrices. By (2), we then see that $(e_1,e_2,\ldots,e_n)$ is a triangular base for $a$. On the other hand, $(e_{\sigma(1)},e_{\sigma(2)},\ldots,e_{\sigma(n)})=(b_1,b_2,\ldots,b_n)$, so that $b$ is triangular in this base also, as wished.