Linux Mint? Isn't that essentially the same thing as Ubuntu or am I missing something? That is, is it the lens search that is the problem or are there other privacy concerns about Ubuntu?
Mint is based off of Ubuntu, but also has a version based off of Debian, as zx2c4 has pointed out. The biggest difference is that Mint uses the Cinnamon desktop environment, as opposed to Unity, which was forked from Gnome 2. Also, they use Nemo, which was forked from Nautilus, which has more functionality and features as opposed to Nautilus.
You are correct: MATE is the GNOME 2 fork that uses GTK2. Cinnamon is a modified version of GNOME3 that uses GTK3 and provides extensions to the GNOME3 desktop so that the default desktop looks and feels like a default GNOME2 desktop.