Paper towels are recyclable and made out of recycled paper, at least. They are the most hygienic solution out there.

I still see the towel rolls around, they're a good option as well. Maintenance for (esp. public) toilets is never not going to be a thing, but it does require a bit more infrastructure to maintain (= washing out etc). But there's companies that will take care of that.

Not offering hand drying is the worst; drying your hands is arguably even more important than washing them when it comes to hygiene.

Anyway beyond that, fixing the hand dryers is also an option. Use larger but slower rotating fans. Dyson's machines have the problem that they have relatively small, high-speed motors.