Your thinking is correct that, in some ways, $x_1, x_2$ are substitute goods. We define substitute goods which have the following property:
$$\left.\frac{\partial x_i}{\partial p_j}\right|_{u=\bar u}>0$$
The case of $U(x_1,x_2)=\max\{x_1,x_2\}$ is that of a boundary solution as the indifference curves are now concave to the origin.
So equilibrium solution is:
\begin{align}
x_i^*(p_i,p_j)=
\begin{cases}
0 & p_i\geq p_j \\
B/p_i & p_i \leq p_j
\end{cases}
\end{align}
where, $B$ is the total expenditure. Note that I have taken equality at both because when prices are same, the consumer will (randomly) choose one the two products and consume only that.
It can be seen that, for a given $p_i$, $x_i^*(p_i,p_j)$ is a step function w.r.t $p_j$ which increases from $0$ to $B/p_i$ as $p_j$ increases beyond $p_i$. Therefore, the function $x_i^*(p_i,p_j)$ is increasing in $p_j$ (though not strictly).