It will certainly depend on the application. Compliance could be as simple for many apps as deleting a user's data manually when you get a support ticket/email from them asking to. You don't need to build automated systems. Same if they ask for the data collected on them.

It would be prudent for these companies to spend an afternoon creating a list of all the places where data is being stored about a user. That would just help if it ever becomes necessary to actually delete data.

See elsewhere in these comments for information on appointing an EU representative. It is not required in most cases.

"Bespoke permissioning" is also required if you have tiers of users with different feature sets (free, basic, premium). So just treat whatever private-data-requiring-thing as a feature that needs consent.

Incidently, the evolution of smartphone permissions has also gone in this way, allowing fine grained allowing/disallowing. You have to expect that you wont have all the permissions you want. The GDPR just makes it so that you don't get to say "all or nothing" for the things that don't need permission. But, the good apps were already doing this anyways.