In short, soft bodies are compressible while cloth is not. All other features are the same.
However, this makes a huge difference in computational speed. To better explain this, I will use an extension of the metaphor CharlesLCharlesL used in his responsehis response.
A Cloth Simulation essentially models the object as a bunch of balls (vertices) connected to each other by fixed-length rods. Thus, for computational purposes, the simulation can treat the internal distances between points as a constant, and only has to calculate interaction with other objects.
A Soft Body Simulation, on the other hand, models the object as a bunch of balls (vertices) connected to each other by springs. So now, not only does Blender have to compute the interaction of the object with other objects, but also has to compute its own internal reaction and the spread of force applied at one point across all of those little springs, which is much more complex.
I don't know the exact complexity of the algorithms Blender uses for these simulations, but it's essentially the difference between a linear relationship and a differential equation.