CCleaner is pretty much a must for general system maintenance (use after a patch Tuesday reboot) and won't break anything like pretty much every other cleaner/optimizer.
As far as privacy goes, why concern yourself with it? So what if Google, et. al. know where I'm browsing. Actually, that's handy because Google Now will recommend relevant reading to me without my getting stuff I don't care about (like anything even remotely related to mass media).