There are a couple of components to consider when comparing Levitate to Flesh to Stone. For one, there is the weight limit. A 500 lb weight limit means that only creatures roughly twice as big as humans would be affected. So giants, dragons, even large bugbears would be unaffected by the spell.
Additionally, there are restraints with space. If you are fighting in a tight space or anywhere with a ceiling, you are going to allow a creature a way of maneuvering despite the spell. This is especially true if you are fighting a creature with large tentacles. Plus there is nothing to stop it from grappling someone and continuing to attack, even if it can't run or maneuver as well as it might like. This doesn't even consider bad guys that might be spell casters with access to fly (a likely target for anything that targets a Con Save), which would completely negate the spell.
Not to mention, if done right, the Flesh to Stone spell has a chance to be effectively permanent, while Levitate will always eventually end.
Finally, the restraint condition as you mention is incredibly powerful. Target has disadvantage on attacks and Dex saves, while your allies all have advantage. That is pretty great. That is effectively -5 to all attacks the creature makes, and +5 to all attacks made against the creature.