You can have it NOT depend on the music file. Like: you can optionally download the music files and place them in skins folder. The worst that happens if the ACS or host uses changemus to a music you don't have is, for the player lacking them, end up in eerie silence or not changing music.
I wouldn't put that burden on the player; if a wad is to use custom music, it is expected of the wad to supply that custom music.
To the file being too large, all it takes is simple editing of the music. I wanted to help Stardust out so I took her four songs and I changed them to mono, looped them, lowered the sound quality (it's negligible but does wonders on file size), and saved them as .ogg. I ended up reducing the new song's sizes into two-thirds or even one half of their original size, and it only takes a few minutes per song to optimize them like that.
As to new Hales with unique attacks...
Kung-Fu Cutman?
No, really, he can attack with a damage-modified Rolling Cutter and be the only Hale with a returning projectile for a mainfire.