Deluxe is a fan term. As is Premium, and they have no consistent definition by the fanbase at all. For a good reason. It's just making a name for a pattern(one that is not consistent).
I thought it meant music too, but to be honest, I don't think the music actually ever mattered. What mattered is that the costume fits the entire body, with no face cut-outs, etc. Shantae is pretty much just a better version of ones like Geno or Isabelle at this point. She clearly had more work put into her than those two(albeit, she's a new costume, not a returning one, so the standards would likely be different compared to just polishing a costume at best, which describes all the returning ones).
Vault Boy is also way more deluxe design-wise. The lack of music is understandable, due to having a lot more generic music(not made for the game), so that's harder to license. Bomberman having no music is odd, but he's a pretty clear Deluxe. He fully encompasses the body and has 8 alternate colors. That's... a lot more special than a song(which we know the songs aren't requirements). Nor is being an Indie.
And that's why it's a fan term. Sakurai never said they were a special category. He never gave them a name or a rule. Because there was never consistency or rules on how it works. Any costumes can come with music, and it seems like Indie costumes just simply having a better chance at it and that's all there is to that. Whereas what are more Deluxe(special) costumes are all about the "cover the entire MIi". They basically aren't the same thing in practice, as we found out once Shantae(who as I noted is still the same type of costume Geno is) was shown off.
Honestly, I feel like it's easier to divide them into two categories; Deluxe(Full Body suit, no face cut-out) and Premium(Music). And some can be both(Sans and Cuphead respectively), whereas the rest only fit one category. If only there was a better term to split them up, heh.