the algorithm is just to have person A cut into two equal slices and then person B choose their favorite slice. it takes just 1 second, which is quite a speedup over the upper bound...
Actually for round cakes you could even make normal (wedge-shaped) pieces by re-parameterizing distance along the line as angle and cross sections as infinitesimal wedges.
Edit: And for the rectangular cake you could slice the cake up along one axis and line those pieces up end-to-end first so that the cross sections would have a reasonable width instead of having slices as wide as the whole cake
Making multiple cuts along a line doesn't seem optimal. Remember that these slices of 3D cake can be of any shape. You can imagine different people liking different fillings or different toppings on the cake.
With 2 people taking 1 second per query you end up with 2^2^2^2^2^2 which is 2^(2^65536) seconds.
I guess if not only the cake has decomposed and the people involved have died, but the universe itself has lost all thermodynamic free energy, I guess technically we are in an envy free state.