I work for a similar organization we are also a non-profit, have union and excluded staff and also use Sage as our accounting software. We switched to DayForce back in 2018 and all three departments; HR, payroll and finance use DayForce. It is quite the learning curve to start but it is great for how much you can customize it. Best of luck finding the best software for your needs.
You may also find some helpful tips in the thread about payroll software.