You can make your save before losing your move...
From the text of the spell (PHB 264, emphasis mine):
A dancing creature must use all its movement to dance without leaving its space...
Note the term "use" rather than something like "lose" or "have its speed reduced to 0". The spell compels you to move your speed within a 5 foot square. Fortunately, from the description of a player's turn (PHB 189):
You decide whether to move first or take your action first.
Even better, if slightly contradictory (PHB 190):
You can break up your movement on your turn, using some of your speed before and after your action.
In this edition, players are given a great deal of latitude on when to use their movement. Since dancing is a use of that movement, you can choose to save before using it up.
It helps to think about what limits your movement speed under regular circumstances. Remember that a round, and thus a turn, lasts ~ 6 seconds. When your move speed is 30 feet, it doesn't mean you are out of breath after running 30 feet, it means that it takes you about 6 seconds to move that distance with enough time left over to do something else. Dancing keeps you from moving anywhere as the clock ticks down, but if you make your save quickly, nothing in the wording of the spell suggests you would be prevented from using the remaining time in your turn to move your speed.
...but you still dance
You start dancing as soon as the spell is cast, with all of the attendant detriments (disadvantage on attacks and Dexterity saves, granting advantage to attackers). There isn't much you can do about that until the start of your turn, but at least you don't have to stay immobilized.
RAW - No, Otto's Irresistible Dance is not a Charm spell
It does not say that the target will be "charmed", and the condition it imposes is significantly different than the description of the "Charmed" condition.
OID:
A dancing creature must use all its movement to dance without leaving its space and has disadvantage on Dexterity saving throws and attack rolls. While the target is affected by this spell, other creatures have advantage on attack rolls against it.
Charmed:
A charmed creature can't attack the charmer or target the charmer with harmful abilities or magical effects. The charmer has advantage on any ability check to interact socially with the creature.
A dancing creature can attack the caster (with disadvantage -- and that disadvantage applies to any attack, not just against the caster) and can cast AoE spells that include the caster and anyone else they choose in the target area with no penalty. They just can't move freely. A charmed character can move freely but can't attack or target the caster.
Furthermore, if it were a Charm spell, it would not be necessary to specify that "[c]reatures that can't be charmed are immune to this spell." That appears to be listed as a special exception.
RAI - No, Otto's Irresistible Dance does not impose the Charmed condition
Jeremy Crawford has tweeted saying:
Being charmed means being subjected to the charmed condition
Since OID does not impose the Charmed condition, the Fey Ancestry resistance to "being charmed" does not apply.
What makes sense?
Webster's dictionary says:
charm: to affect by or as if by magic : compel
Magically forcing someone to dance seems to fall completely within that definition.
I would give those with Fey Ancestry advantage on saves against all enchantment spells that compel the user to do something that is not their own free choice. This includes many spells that do not specifically say they are "charms" or that they impose the "Charmed" condition, such as command, compelled duel, and yes, Otto's irresistible dance. I believe those all fall within the common sense and dictionary definitions of "charmed" in this context, and there's nothing in the description of Fey Ancestry that says it only applies to things that grant the "Charmed" condition.
Best Answer
"The target begins a comic dance..."
While you are casting the spell, you choose the target. As soon as casting the spell is complete, the target "begins a comic dance" (unless it is immune). The rest of the spell description is about the effects of this dance.
Some of the effects of its dancing happen immediately:
Other effects 'begin' on the target's next turn. It is not that these effects are delayed, merely that the things they affect are not relevant until the target's turn, when it first has movement and the ability to take actions:
It is a bit confusing that the immediate effects and the effects that later happen on the target's turn are interspersed in the text, but since we know that the target immediately "begins a comic dance", and since all the effects of the spell are consequences of this dance, we can apply each of the effects at the first moment they become relevant.
Because the target is dancing for the entire duration of the spell, some effects that normally would not happen until the target's turn may be "moved up" before its turn, depending on circumstances. For example, if another creature left the target's reach after the spell was cast but before the target's next turn, the target would be at disadvantage to hit should it choose to make an opportunity attack. Another case would be if the target was granted movement before its next turn, such as when a spell effect used its reaction to force it to move. In this case, the "must use all its movement to dance" would take place as soon as the other feature granted it movement. Cf. Does the target of Otto's Irresistible Dance followed by Dissonant Whispers (failed saving throw) move as a reaction or just keep dancing in place?
The OP asks:
As explained above, yes! The spell is particularly powerful when the caster can grant advantage to their entire team on a target before the target can even get a save against the spell. Compare this to, for example, web, where the targets are not restrained until their own turns, at which point they have a chance to save, so unless they fail there is no direct benefit to the web-caster's team.
However, automatic full-team advantage occurs only when the caster's and the target's initiatives happen to 'bookend' the rest of the caster's team's initiatives, and bear in mind that this is a sixth level spell that targets a single creature.
I believe that it remains an open question of whether a target could, on its first turn, elect to use its action to end the spell before it moved and, if successful, could then use its movement as normal, or whether all of its movement is immediately used up as soon as its turn starts and before it has the chance to make the save.