The best place to start, in terms of protecting your data from the government, is the Electronic Frontier Foundation's annual "Who Has Your Back?" list. The EFF reviews Internet companies (cloud storage, broadband, social networks and beyond) on a "star" system based on six categories.
You should be happy (or disconcerted...) to know that Gmail came in at a strong five out of six stars. There are other options out there, of course, but it may take some e-elbow grease to find them.