They are not "simple and straightforward to implement" for two reasons. First one, the problem domain is not simple and straightforward to implement. It may be surprising, but it's only because we've never learned to treat PII with proper respect. Second one, it's because businesses did their best to avoid and abuse privacy laws previously, so the new law has to counter the usual workarounds.

Yeah, it might be getting harder making a startup working on personally-identifiable data - even if it's not doing anything shady. But it's also hard to make a food or healthcare startup; you can't just "move fast and break things" there either. In EU, PII were finally granted the status of something actually important.

As for startups that depend on abusing user data, I'm very happy they have problems now.