As I said up above (somewhere) The new permissions system is a drain that shows that a new idea is not often a good idea.
Be warned! This may take a little bit to read, since I'll be talking about the history of android, and more! Go and grab a drink!
You good? Alright, dig In.
The origins of the new permission system
When Google began working on a way to forcibly grant and deny permissions on-the-fly, it was Android 4.3. It was a buggy mess, so they hid it. It can still be used, however, by creating a shortcut to the app ops settings menu. This menu was very similar to the current apps menu, but tapping an option immediately brings up the permissions options. You also had to discover the permissions before you could toggle them, and it was a buggy mess since apps wondered what the balls is going on because you disabled something, and inconveniently crashed. Yay.
The system was removed once modders had found it (so it was removed in 4.4),1 but made its return in Marshmallow. It looked really good - you could finally choose if things like Facebook could grab your location (though it did ask nicely). Even some Google apps, like Hangouts, aren't safe from your decisions. But then we hit the issue - the system is still broken, just in a new way: the permissions were heavily tweaked.
You want Stack Exchange to login via Google? It needs contacts permissions (though The devs at SE fixed that on their end).2 Want To upload images onto Facebook? It needs to see all your files. Why? Compression. Permissions are now granted in groups, where asking for your Google account also allows apps to see every contact on the device. I doubt that was intended, but the removal of most permissions meant that the had to simplify the playing field; most removed permissions were just shoved into super-general groups.
Some of the permissions have been removed because of new SDK's. GET_ACCOUNTS
Now triggers a new SDK which allows for Google sign-in, but falls back to doing it via contacts permissions if an app does not support it. That explains that one (including how the SE app was finally fixed), but some of the others don't get that treatment. AFAIK, Apps can just casually read the dictionary regardless through the keyboard. Most other permissions Izzy mentions seem to correlate with modified groups: Most fit into the 'Modify system settings' Godmission (permissions separate from the main ones) and 'usage access'. Some others are handled by apps themselves.
So, Anything not given a new home was killed off. Sometimes, this made sense (we only need GET_ACCOUNTS
to trigger the SDK) While other times, it made you want to put a bullet into your phone: oh yeah, I'll just let you access my contacts, you seem fine. Sure, access my calls and waste my money. (Hopefully no one is that dumb. Hopefully.)
At first, I thought yay! Simplification! But it allows seemingly legitimate apps to do illegitimate stuff A LOT easier. Your Minecraft hack tool which wants your Google account is probably also robbing your contacts. And selling them.
This is then compounded by the Lockdown system for permissions, that allowed you to fine-tune app permissions. It's great, but it doesn't work. At all. It also is inaccurate (it e.g. says that Stack Exchange reads my SMS'. No, no it doesn't) and is just plain awful.
But what does that mean for my privacy?
I personally think one of two things:
The new permissions system was designed to allow simple, quick changes for the purpose of security. Permissions are now granted in groups, which explains why some are removed: Google thought that leaving them under one big header was a good idea (and for the end-user, I see why: controlling each individual permission could get tedious.) Of course, like communism, it was only good on paper; in reality, it's a shamble that they don't want to admit to. Fair enough.
However, they could be doing this to force more apps to use Their SDK to break alleviate suspicious permissions (Don't blame them) and therefore make more money. It's proved they are doing so (and are trying to make Android less open-source) which disgusts me.
So for the end-user, it's like a little bit of iOS - by which I mean something that looks good, but is crap. But can it be fixed? Kinda.
The "Work-arounds."
Method 1- Xprivacy (ROOT NEEDED BOI)
Xprivacy does work on Marshmallow, according to its devs, of course. It requires messing with all sorts of fiddly bits on MM now, and there is verified boot. Which is a pain, since you'll probably get a red or yellow warning, which may prevent boot. (Depending on your luck, and how much messing you have done.) But if you can get Xprivacy working, its easy enough.
Due to the 'Wont boot FULL STOP' attitude N will apparently take, it may even be more of a nightmare to get working on that.
2017 EDIT - Xposed devs are working on getting around all of this (yay!) If i find the post on XDA, I'll link it
METHOD 2 - Go full Lockdown on everything.
This is really fiddly, but allows for maximum control (as far as that's possible). You grant app permissions when absolutely needed, then make a mad dash to turn them back off again. Probably will be easier once Nougat drops on more devices, so multi-window can be used.
METHOD 3 - Don't upgrade (which I'm dubbing the "Izzy solution")
If you did look up when I told you to, you may have noticed what Izzy's method is: You simply refrain from upgrading to Marshmallow or Nougat. Boo-Hoo, I know, but neither are game-changing, really. Give it.... Six months, and most the crap for N will be on the play store, if you really want it. So, the Izzy solution means sticking with the definitely capable 5.1.1 or lower. I can live, and so can you.
METHOD 4 - NUKE IT FROM ORBIT.
(Just to please the masses. FYI, this would be impossible.)

Or, ignore it. Your call.
EDIT Izzy found a link to a Stack Overflow question That explains that Credentials, Like Logins for Signing in on various apps, fall under a 'normal permission' (protection-level "normal") – i.e. any app can access them without you knowing. Luckily, some apps and logins will let you remove this through their account managers, Depending on how malicious the Dev is trying to be.
EDIT 2 I forgot to say you can remove apps from accounts :) I'll be using The Google accounts and Facebook app accounts systems as examples, as they are the most used.
Google accounts
- Head to accounts.google.com or open the Google play settings (varies by device, usually a cog with a g in it)
- Find apps/Connected apps/connected apps and services (again, Varies)
- Find what you want to remove, and click 'remove'
DONE!
Facebook
- Login on the site
- Head to account settings > apps
- Find the target app, and click/tap remove.
Done!
Hope that helps! If not, just drop a comment, you know the drill. I'll be working on it anyways. Done, but still let me know if I missed something!
1 There were different attempts made by Google to "hide it better", and different versions of AppOps frontends brought it back then for 4.4 and 5.0, but no further
2 Apparently, apps can voluntarily use a new SDK that allows Google sign-in without the contacts permission. See here for details.