First of all instead of taking
Cross(WorldUp, Front/LookAt) you can use Gram-Schmidt orthogonalization to produce an orthogonal vector that's close to the WorldUp vector. Then you take the cross of this orthogonal vector and the look at to get the side vector. However as you mentioned this'd fail if the vectors are parallel.
Hence the usual solution is to pick another vector that's not parallel to the look at one and again use Gram-Schmidt orthogonalization to produce the orthogonal vector ( camera up) and then take the cross.
The maths is like this.
CameraUp = c
WorldUp = w
LookAt = l
c = w - ( (w.l) / ||l||^2 ) * l
What it does is this. We know that world up isn't pure orthogonal to the look at vector. So we take the projection of world up onto the direction of the look at vector. Subtract the parallel part of this projection from the world up vector to obtain the remaining i.e. the orthogonal part. This vector is closer to the world up but is purely orthogonal to the look at vector.