Tile-sets is the wrong way to go about it. To do it well we need a ‘super map’ then reduce it down to a single path for each mission.
As a simple example, take a piece of graph paper, each cell is a room, each room is connected to adjacent rooms. Some rooms are just for traveling, some are event rooms, some are boss rooms, some are map start rooms, some are map end rooms. Nothing random yet, everything is hand crafted, and the adjacency make sense.
Now to generate a kill mission, randomly pick an end room. Then randomly choose a nearby boss room. Then randomly pick a path between the 2. From the boss room, pick a random nearby event room. Randomly pick a path between the 2. Now pick a nearby start room, and pick a random path between the 2. Now block off all of the unused rooms. Boom, mission done. Tie in some voice over describing it and you have something that feels good, looks good, and you’ll be hard pressed to every play the same exact thing twice.
Best part is you can start small, like a 5x5 grid, and add to it over time. As new areas are added, up weight the RNG for them to be picked. If rooms are buggy, they can be removed from the RNG until fixed.
Now in reality, instead of a nice box shaped rooms, it’s more complex than that. That bridge in throneside would be an event room in one of the cells. Except it doesn’t just have 4 connections, it has like 10. Some missions would have you crossing the bridge, others would have it visible but not reachable, others would not even have it.