This sounds like two different problems -- W3 required and `sepia-rebuild' getting stuck. If possible, could you give me a recipe to reproduce both problems, or at least describe the symptoms as precisely as possible?

First, it shouldn't require w3 anywhere, and the dependency on emacs-w3m (a completely different package, confusingly enough...) should be optional. If it's not, that's a bug.

Second, you may have to call `sepia-repl' before `sepia-rebuild' to make sure the inferior Perl process has started. I should fix `sepia-rebuild' to check for the inferior Perl and start it, but most operations don't require the xref database to be built, so I don't test this out much in day-to-day use.