MEDUSA

Sounds interesting, honestly I think it would be cool if there were things like mini bosses that you could find randomly on islands. Not necessarily just medusa, but other random things that could have interesting and unique mechanics. Something that would be rare to find and would just hang out on a large island, and there would only be one of them in the server at a time, but unlike the ancient megs there wouldn't be a way to find them.

Or maybe there would, idk, but I like the idea of a boss fight with interesting mechanics like that that you wouldn't intentionally look for but if you do find them then killing them would be fun and worthwhile.

There could be something like you mentioned with turning people to stone, although I imagine it would have to act more like the eelectric stuns or maybe even like how throwing water on a golden skeleton slows them down and weakens them.

There could be an enemy like a special ocean crawler that summons other ocean crawlers and can use all of their abilities.

There could be a boss that is constantly surrounded by a smoke or mist that makes you rely on your ears more than your eyes (more interesting and harder to see through than the ashen lord one though that one doesn't really do anything).

There could also be one that has like clones or illusions or something.

Those are just a few random ideas but the gist is it could be cool to have some variety in enemies that are rare and pure luck to find but fun and drops something cool.