Have heard only good things about them. However I think they work with larger Retail Retargeters like Zappos and specialize in dynamic creative optimization. Others you may want to look into if you are just getting into the Retargeting space would be AdRoll, Simpli.fi, and Sitescout
Criteo is great, plus they tap into the FBX (few do these days). You do need some decent traffic, but I think the bar is as low as 50k unique visits per month, perhaps a tad lower if your brand is strong and conversion rate is high (they need sales data to optimize outcomes, if you're small, the gyrations of anyone's algo seem excessive, the feedback loop lacks velocity, and there's little that can overcome that). If you've got a product datafeed running in Google Shopping, and you've got well over 50k UV / mo, I very highly recommend Criteo. Like everyone else, they're not perfect (the lack of a "pause my ads" setting continues to baffle my team), but they're definitely on our short list of best providers.
Thalamus, the dynamic creatives are what drew me in. I currently use dynamic ads with Google and saw my competition showing dynamic ads in Facebook (at first I assumed AdRoll) then I saw them on some premium sites. I think it was MSN above the fold. Thank you for the other recommendations, I wasn't familiar with them.
Rhino, cool, thank you for the input! Definitely getting enough traffic and we do have a shopping feed, so that's good. Not being able to pause is a little weird but, I could live that.