I don't own a start-up (my little software company is 21+ years old now), but I've had good luck with QuickBooks Online. Available anywhere you have a full browser (with weak iPhone/iPad mobile access), and has full payroll module (which I haven't tried). We do use the online payments module for all charging; works quite well, and with online bank accounts, it's easy to keep things in synch.
QuickBooks for my accounting and PayChex for my corporate payroll.