I've answered "map first", but that's only partly my way. I prefer physical geography first - landforms, climate, land cover, drainage. With that mapped, maybe even not in exquisite detail, I can come up with some story. not "John left the castle, setting off on the King's Road into the sunset...", but the big sweep of history, society, culture. Then I'll go back to mapping and devise some politics - borders, habitation, transport, land use. Then that level of geography suggests story opportunities.

While it's iterative, I usually don't backtrack on the maps. Maybe that's a measure of the strength (or NOT) of my plots - the world having attained more solidity in my mind than what I have to say in a story.

Of course I do have a backlog of story and plot fragments, characters and situations. As I wander around a new setting, one or more of them will crawl out of my memory and slap me upside the head. So would that be "story first"?