Ask HN: Payroll, HR and Benefits Software/Service for Startup?

Looking for advise for Payroll, HR and Benefits software/service.

We are a small startup in the Bay Area, which obviously expects to grow big. We have several remote employees who are in different states, so tax and benefits compliance needs to be supported.

We also expect to bring in consultants for short/long term.

Some of the options that we're looking at are (in no order): Gusto, Zenefits, Paychex. ADP I've heard is great, but looks like they are targeted at large companies.

Thanks in advance!!