I suggest Zoho one. It's been in service for many many years. It's not as feature rich as Google or MSFT, but their service is fantastic and gives you all options a small business needs (office, marketing, CRM, sales, HR, Finance among others).
But avoiding getting locked out of your account and having to post on HN to get any support from Google? Priceless.
I don't know if Zoho has great customer service, but I cannot imagine it is worse than google's.