You can finish the story first if you want and do the side missions later since nothing is missable, but I would suggest do both simultaneously or else in the end you will be left with around 61 side missions which would end up feeling like a drag
Once story is done, liberate all the outposts and camps so that the map reveals all the undiscovered locations.
For collectibles you can unlock the skill with which the guiding wind will guide to your next shrine, fox den, bamboo strikes, etc. that you are missing, so no need of any guide to be followed. ( Most probably, in the end you will be missing one haiku and one hot spring since they won't be marked in the map with the "?". Just talk to the lady near the spring and a hat guy near the mountain of Hiyoshi springs for both of them respectively).
Also do the Mythic Tales as soon as they are available, has some of the best quests in there and also unlocks crazy skills.