I think the Senators have a problem with Google's size because they analogize it to other corporations of the 19th and 20th centuries whose size went with considerable power. Google does have plenty of influence, but it does not have the kind of legal power through capital ownership an old-time vertically integrated conglomerate had or that a telecommunications company often has now.
Migrating from Google to another service, or suite of them, wouldn't be terribly difficult, especially since they seem to be fairly good about data portability.