Profiles and Roles are 'different' for want of a better word. Complementary even.
OWD is the foundation which decides whether our data is setup in Private / Public Read Only or Public Read Write. This is the most restrictive data setting.
When the OWD is Private, Sharing Rules become available to open up the OWD data restrictions to groups of users or roles and subordinates. These can either be ownership based or criteria based(with some limitations)
Another way to share data is through Apex sharing where you can programmatically insert share records based on custom logic too complex to encapsulate as Criteria Based Sharing Rules.
Profiles control what you can do with the data that is visible to you, certain administrative permissions and of course which objects in the schema you have access to.
Field Level security for example lets you control at a Profile Level which fields are visible or read only to certain profiles.
The View All Data and Modify All data permissions on the Profile are exceptions because they bestow 'SuperCow Powers' on the users with that Profile. Hence why they are normally granted only to Full System Admins.
Permissions sets are a way to provision profile permissions in a modular fashion so you can group a bunch of related permissions.
Permission sets supplement the permissions already granted to a user by virtue of their user profile.
Additionally Profiles also control which Apex Classes and Visualforce pages you have access to.
In summary, unless its via Custom Visualforce, an Insufficient Privileges error when trying to access data will be down to the Role Hierarchy.