There are several differences:
- Memory allocation
- Code reusability and OOP
- Testing
Memory allocation
For static class members (static vars and constants) memory is allocated when you first call the class. For instantiable classes, it is allocated only when you create an instance. That doesn't make a lot of difference in trigger context.
Code reusability and OOP
Classes with static methods
With static methods, all the re-usable code has to go to utils classes. That may lead to having classes, that don't have a specific responsibility. These classes violate the single-responsibility principle and generally considered a bad practice. This kind of classes makes it difficult to navigate in the codebase.
Singleton handlers
Singleton handlers are instantiable, which means they can use inheritance. You can move all the code that is re-usable by several handlers to a super-class. This reduces code duplication and makes it easier to read through code and navigate over a codebase.
Testing
Classes with static methods
If you test a handler you need to go through all the logic in all the handlers, unless you have a custom-built deactivation mechanism. If you have one - you can deactivate pieces of code that you don't need to run.
Singleton handlers
Since singletons are instantiable you can stub them with Stub API. With that, you can isolate the piece of code that you want to test. That works well when you need to insert some data and do some manipulation, but you don't want the real logic to run. Or when you're writing your own trigger framework and need to test the order of execution and stuff like that.
You need some kind dependency injection to use the stubbing though.
Conclusion
In my experience, I saw a lot of codebases and libs that rely on classes with static methods. Those may sometimes look nicer when you're writing code, since you don't need to create any object instances. Also, it's easier to think about logic as a set of instructions and do it in a procedural programming way. But OOP came around for a reason.
Codebases that rely on static class members are harder to maintain, harder to navigate, and they do not encourage proper code composition in a way OOP does.
I prefer going with the OOP way not only for handlers but for pretty much everything. I think the only places I use statics is where you have to use them, like AuraEnabled or RestResources.
Hope that helps. Feel free to ask any questions.