How are exactly $u_j\partial_ju_i$ and $u_i\partial_j u_i$ related?

And what is their relation to ($\boldsymbol{u}\cdot\nabla)\boldsymbol{u}$ and $\boldsymbol{u}\cdot(\nabla\boldsymbol{u})$ ?

$$[\mathbf{u}\cdot(\nabla\mathbf{u})]_{i}=u_{j}\partial_{i}u_{j}=u_{x}\partial_{i}u_{x}+u_{y}\partial_{i}u_{y}$$

$$[(\mathbf{u}\cdot\nabla)\mathbf{u}]_i=u_{j}\partial_{j}u_{i}=u_{x}\partial_{x}u_{i}+u_{y}\partial_{y}u_{i}$$

from this it would seem they are different, but:

$$[(\mathbf{u}\cdot\nabla)\mathbf{u}]=(u_{x}\partial_{x}+u_{y}\partial_{y})\left(\begin{array}{c} u_{x}\\ u_{y} \end{array}\right)$$

$$[\mathbf{u}\cdot(\nabla\mathbf{u})]=\left(\begin{array}{c} u_{x}\\ u_{y} \end{array}\right)\left(\begin{array}{cc} \partial_{x}u_{x} & \partial_{x}u_{y}\\ \partial_{y}u_{x} & \partial_{y}u_{y} \end{array}\right)=\left(\begin{array}{cc} \partial_{x}u_{x} & \partial_{y}u_{x}\\ \partial_{x}u_{y} & \partial_{y}u_{y} \end{array}\right)\left(\begin{array}{c} u_{x}\\ u_{y} \end{array}\right)=\left(\begin{array}{c} u_{x}\partial_{x}u_{x}+u_{y}\partial_{y}u_{x}\\ u_{x}\partial_{x}u_{y}+u_{y}\partial_{y}u_{y} \end{array}\right)$$

from this it would seem that they are the same. I am quite suspicious about my definition of $\nabla\boldsymbol{u}$. Could someone clarify this?

Your math is correct, $\left(\mathbf u\cdot\nabla\right)\mathbf u\equiv\mathbf u\cdot\left(\nabla\mathbf u\right)$. This should make sense because the commutative property holds for dot products.

Personally, I prefer to view $\mathbf u\cdot\nabla$ as an operator that acts on something (in this case, a vector, but it could be a scalar or higher tensor as well). Thus, I would use $\left(\mathbf u\cdot\nabla\right)\mathbf u$ over the other way. This also has the added benefit of viewing the index-form more clearly: $$\left(\mathbf u\cdot\nabla\right)\mathbf u\equiv u_i\partial_iu_j\tag{1}$$ In this form, you can see that the indices of $\mathbf u$ and $\nabla$ must be the same due to the dot product.

The confusion, it seems is from your alignment of indices. Equation (1) is not equivalent to the 2nd way you write it: $$u_i\partial_iu_j\not\equiv u_j\partial_iu_j$$ The latter term, $u_j\partial_iu_j$, is actually a column vector times the matrix $\partial_iu_j$ (making a row vector) while the first term, $u_i\partial_iu_j$, is a row vector times a matrix (making a column vector, which is what you actually want as a result).

The problem is in the way you wrote your last equation as a matrix multiplication.

You have $$[ \textbf u \cdot ( \nabla \textbf u) ]_i = u_j (\partial_i u_j) = (\partial_i u_j) u_j,$$ so if you want to write this in matrix form you have to multiply the vector $\textbf u$ at the right, as a column vector, i.e.

$$[\mathbf{u}\cdot(\nabla\mathbf{u})]=\left(\begin{array}{cc} \partial_{x}u_{x} & \partial_{x}u_{y}\\ \partial_{y}u_{x} & \partial_{y}u_{y} \end{array}\right) \left(\begin{array}{c} u_{x}\\ u_{y} \end{array}\right),$$ where the derivatives are intended to act only on the adjacent $u_i$.

Anyway, I don't see where the covariant derivatives comes in here. The $\nabla$ you are using is simply a gradient, not a covariant derivative.