Where should I host my email

I know guys we had several discussions about this in the past, but here's the thing:

Premise: I want to use my own domain for my private emails. I am not brave enough to host my own mailserver. Conclusion: I purchased webhosting incl. email server from a EU based company where DKIM and SPF are properly configured.

So far so good, worked for quite some time, but now:

Problem 1: (more severe): more and more of my sent emails go to the recipients spam folder, this seems especially true for large providers such as gmail.

Problem 2 (can handle locally, more of an annoyance): incoming spam is increasing as the webproviders spamassin doesnt seem to work quite well.

So my question is this: Where should I host my email to maximize acceptance of sent mails by major mailservers?