Ended up putting the domain account that runs the c2WTS service in the Local Administrators group. Restarted service and app pool that hosted the Security Token Service. All seems to work now.
Edit to tell the whole story
There was actually a lot more going on than just this one fix that I think might be beneficial to the greater Sharepoint community. I'll tell the entire story in the hopes that it helps someone else out.
To start out, we care a four server SP-Farm, Admin, Search, Workflow, and Web (all on-premise). What I was trying to do was enable end users to install apps onto their MySites page. Specifically, I was trying to enable the free app, Documents Shared with Me. I had to log into Sharepoint as a Farm administrator in order to install the app so that it would appear as an App I Can Add. That was straightforward enough. The problem then became having users go to their My Site and try to add the app.
As my user account, I would get the You Can't Add This App Here message. Completely unhelpful message. After viewing the ULS logs, it was apparent that there was a security problem on the call back from the office. The C2WTS service couldn't generate a token for any of the users. Our C2WTS uses a managed service account per the Wrox Sharepoint 2013 Administration book. I've read where this has to be the local system account and I now understand why. If you run the service as Local System, there will not be any security permission problems because the service first checks the WSS_WPG group on the local computer for whether the user can call this service or not. So the first hurdle to overcome is to get all your sharepoint users as part of the WSS_WPG on all your servers that run C2WTS.
The second hurdle was that the service that the account runs under Act as part of the operating system, Impersonate a client after authentication, and Log on as a service rights on all the boxes that have C2WTS.
The third hurdle was setting up the user account that the service runs under with a Service Principal Name. This is required. Do not skip this. You can choose to use any endpoint (I chose WWW), this doesn't appear to matter, just as long as you choose one. I ran
setspn -S SP/C2TWS DOMAIN\SERVICEACCOUNT
Where DOMAIN is your domain, SERVICEACCOUNT is your service account. After you've run that against your user, go into AD and click on the delegation tab. If you don't see the delegation tab, your setspn statement didn't work. Here's where you can Trust this user for delegation to specified services only / Use any authentication protocol. Now, if you are running a single server, you only need to add one entry here. But if you are like me and manage a small farm, you need to add an entry for each machine in the farm that runs C2WTS. Again, you don't have to be picky about the service you specify.
With that all set up, I would recommend a server reboot of every server in the farm. I experienced some randomness with regards to being able to add an app and I imagine it has to do with services caching credentials. But that isn't the end of it.
My account was able to go to the My Site and add an app. But a basic account wasn't able to. They would still get the 'You can't add this app here' message. The final piece of the puzzle was to modify every file in the C: \ Program Files \ Common Files \ Microsoft Shared \ Web Server Extensions \ 15 \ directory that begins with AppPermissionProvider and contains the value TenantAdmin with SiteCollectionAdmin. Do it in all the files on all the servers that operate as a WFE. If you see that value, replace it. I believe because my account was a farm administrator, I could add apps. But when a basic user tried, they'd get the error message. If you inspect the network traffic, you'd see on the JSON object that is returned that prerequisites met is false. So this means that the user can't get past the permissions because they aren't a tenant admin. But every user is a Site Collection Admin on their own my site. So bumping down the permissions seems to be okay.
And if you get it working but the next day it doesn't work, check that your AD policy didn't rip out the permissions you set on the Local Administrator. After resetting the permissions reboot all servers. I have a feeling that caching across servers kept me pulling my hair out for the better part of a day.
Sources for you to try:
Tenant to SiteCollectionAdmin
More Tenant to SiteCollection
App to troubleshoot permissions on C2WTS