Requiring Chrome and the search widget to be uninstallable on Android in exchange for access to the GMail app is definitely a step too far, straight out of Microsoft's playbook.
At least Android allows sideloading apps though. We know that privacy permissions can be done correctly at the OS/Api level, even web browsers do it. It's crazy that Apple can be complicit in enabling Google's search monopoly and face no repercussions for it's app distribution monopoly.