Even if they complied with your erasure request and deleted everything from all their servers and their backups (spanning the world over a decade), think of all the non-EU third-parties who have your FB data already
GDPR isn't only about data deletion, but also about the transparency of data handling strategies. There was a "nightmare GDPR" letter HN post a couple of days ago that illustrates some of those responsibilities.
I wonder if GDPR could be applied to companies I don't have a relationship with but have my data (i.e. CA-type data collection companies)?
Sure. That's already possible in Germany, where any company has to provide you with the details of their knowledge about you once a year for free: https://selbstauskunft.net/
The GDPR basically states that a company have a relashionship with you if they have data about you.