I'm not sure how this is taught elsewhere, but to me it is much easier to understand step two in terms of the invariant factors of the associated characteristic matrix (so of $xI-A$ where $A$ is the matrix representation of $\phi$).
So here is a small explicit example where the matrix is already in rational canonical form, but I will point out the different steps:$$ A = \left(\begin{matrix}0\\&0\\&1&0\\&&&0&\\&&&1&0\\&&&&&1\end{matrix}\right). $$
The minimal polynomial is $x^2(x-1)$, so step 1 is to find the blocks associated with $x^2$ and $x-1$, this you say you have no problem understanding, and so we have $$A_1 =\left(\begin{matrix}0\\&0\\&1&0\\&&&0&\\&&&1&0\end{matrix}\right)$$ is associated with $x^2$ and $$A_2=(1)$$ is associated with $x-1$.
Now in the given example the decomposition of the space associated with $x-1$ is finished, but we can decompose the space associated with $x^2$ further: it should be easy to see that there are three linearly independent characteristic vectors associated with this space, and therefore we must have three indecomposable subspaces (in this example you can already see the three matrices associated with each of the subspaces, and in fact since the minimum polynomial is $x^2$ we know the largest subspace must have dimension 2, and since $A_1$ is order 5 there is then really only one way to split it into 3 indecomposable subspaces)
BUT there could be more complicated scenarios where it could be more difficult ...so how to construct these...for me the easiest way here is to use the Smith normal form of $xI-A_1$: $$xI-A_1 = \left(\begin{matrix}x\\&x\\&-1&x\\&&&x&\\&&&-1&x\end{matrix}\right)$$ has Smith normal form $$ \left(\begin{matrix}1\\&1\\&&x\\&&&x^2&\\&&&&x^2\end{matrix}\right).$$ If you read the link you will see that this form is determined by dividing the greatest common divisor among successive orders of subdeterminants of the characteristic matrix, and it always gives you a diagonal form with the "invariant factors" on the diagonal. These factors have some amazing properties including that they are invariant with respect to the underlying field, i.e. a matrix over the smallest field in a chain will have the same invariant factors as all containing fields.
Each invariant factor also divides the next and the last entry on the diagonal is the minimal polynomial. Multiplying the invariant factors yields the characteristic polynomial, but I digress...
To make a long story short, from theory it can be proved that the companion matrices of the nonconstant diagonal entries of this Smith normal form gives you exactly step 2, so $C(x), C(x^2), C(x^2)$ are the matrices associated with the nondecomposable subspaces we are looking for: in this simple example we already have these three blocks on the diagonal.
I hope this helps to answer your question: so typically for me finding the rational canonical form involves calculating the Smith normal form of the characteristic matrix...it gives you the number and dimensions of the $U_i^{(j)}$ as you would need, but it does not give you the change of basis matrix that would produce the transformation...in most cases this is not necessary though.
Final remark, the $U_i^{(j)}$ are formally known as elementary divisors. You can replace step 1 and 2 by calculating the Smith normal form of $xI-A$ directly - as the Smith normal form yields the elementary divisors (a good source that explains this very clearly), and then you can apply 3 directly.
Best Answer
Yes, you have two possible rational canonical forms given the information you have. Both the matrices you wrote have minimal polynomial $(x-1)^2$ and characteristic polynomial $(x-1)^4$.
However, what you wrote regarding finding the rational canonical form is not correct. In general, you cannot determine the rational canonical form of a matrix only from the minimal and characteristic polynomials as your example clearly shows. You need to know the whole set of invariant factors of which the minimal polynomial is only one of them.
To justify that $A$ has one of the two possible canonical forms above, let $a_1 \, | \, a_2 \, | \, \ldots \, | \, a_k$ denote the invariant factors of $A$. The highest invariant factor is always the minimal polynomial so $a_k = (x-1)^2$. The characteristic product of the matrix is the product of the invariant factors so we have a priori two options:
$$ a_1(x) = (x-1), a_2(x) = (x-1), a_3(x) = (x-1)^2, \\ a_1(x) = (x-1)^2, a_2(x) = (x-1)^2. $$
The first option corresponds to your first matrix and the second to your second option. For more details, see section 12.2 in Dummit and Foote's Abstrat Algebra.