If you use the email service of a company, you have to trust those guys.
I switched recently from gmail to lavabit and I think this is a step up, but
it's not the perfect solution.
Of course it's better to use an email provider which claims to respect your
privacy than just a service like gmail.
Chance of getting a victim of privacy violation is lower;
nevertheless, a good digital society should not need to trust a company with
closed eyes.
Therefore, I would really love to see projects like "freedombox" succeed.
It's the plan of a simple and easy-to-use device which allows non-technical
persons without great effort to host most services on their own;
We need such a thing, and everyone should have one:
own mail server, own cloud server and so on.
At the moment I use duckduckgo and startpage as a search engine.
You mentioned concerns about last one. What are these concerns? Can you
explain / give more links?