I hate Criteo. It freaked me when I first noticed, as well. What's particularly annoying is when I get ads from a website I've only just left. If I wanted to buy something from them, I would already have done so, and the only other alternative is I didn't see anything I wanted, so what's the point of advertising it again? Keep getting this with Marks & Spencer. If I've looked at a range, but not bought (or even if I have bought) it keeps going on about it, after that, wherever I go! Shut up, M&S: just because I browsed your jumpers or whatever this morning doesn't mean I need reminding another ten times, in case I've forgotten what I just looked at!
Choose the opt-out on the website you've already linked. It does work, but you have to remember to redo it if your cookies get deleted (accidentally or on purpose).
It's not really any more sinister than any other use of tracking cookies - it's just a damn annoying application of it!