The trick here is to set the Random parameter in the controller before we transition to the Blend Tree. This way we don't see the sudden change in the animations (the animation is already chosen before we start playing it).
We are still using the float type parameter in the Blend Tree because we cannot use integers in Blend Trees in Unity.