After 100 hours of a crash-free game, I'm now crashing everytime I try to access the map. If I press "m", instant crash to desktop. My save is about 10mb and this is roughly what happened:

I) I started Boethia quest
2) In the dungeon, started to crash for no reason (first sign of trouble)
3) after exiting the dungeon, try to fast travel by accessing map, crash

Vanilla game, no mods. Tried reverify cache and reinstalling game.

Did you, by any chance, modify your Skyrim.ini prior to the map crash occurring? I once had the exact same thing, crash whenever I touched the m key, then tried everything to fix it until it turned out that a line in the ini that removed bloodsplatter on screen from damage for some peculiar reason made the map screen crash. Have you tried renaming your current Skyrim.ini and SkyrimPrefs.ini to something else, then let the game generate new ones and then see if the crashes persist?

That was it. I added this line to skyrim.ini:

[ScreenSplatter]
bBloodSplatterEnabled=0

And I did it just before Boethia (and here I thought the quest was bugged). Mea culpa. Thanks for your help. And the guy that did the tweakguide in the sticky needs to remove that tweak.

yeah, I get that too when I added that to my ini file. I can turn off the gore just fine but when I add that one it crashes every time I use the map. Tried it on my PC and on my wife's laptop and got the same results.

I'm glad to hear that it solved your problems I'm also hoping that either Bethesda fixes that .ini line, or people on forums inform one-another not to use that particular tweak. And it just seems so random as well, that a bloodspatter removing tweak would crash the map screen of all things. When it happened to me, I was at my wit's end, changing and removing all .ini lines except that one, because it made no sense. Only after generating a brand new file and later reading about it from an obscure thread did I realize what had happened.