Good suggestions, gives me something to think about!
My main reason for having these milestones is that they basically serve as events that unlock certain part of the game + make up the most crucial parts of the story (this might be meeting certain character, finding certain item, investigating a certain location, etc). The minimum any game can have in terms of this are spacial based milestones where simply getting a certain distance from the start (or similar), triggers the milestone. Of course, milestones could be removed altogether, but that would mean there could not really be an end state (that being a milestone). And I am honestly not confident enough to try and design that
So I still want to rely on some sort of milestones, and I agree when you say:
I'm a bit uncomfortable with the idea of requiring the player to have done certain things before they are allowed to progress
This is exactly what I am trying to avoid, by making the milestones in such a way that it is always up to the player if they want to progress. One way to visualize it is that I want big glowing "NEXT CHAPTER" button, that the player can press anytime they please and then surround that with interesting points of interaction (something you covered). To make this engaging, the collection of interactions would change when the player chooses to press "next chapter" and thus needs to consider what to do with more care. Also future states can depend on past interactions.
Now I am willing to do it this obviously, but want to have it more woven into the story. So i need to have some sort of device / design thinking that provides this structure within the game context. That is really the core of what I am getting at.
We are considering having a fairly short "base game", where most of the engaging and interesting things happen when the player strays. But there still needs to be milestones placed. And these milestones should:
1) Feel seamless to the player and be part of the game world. In a perfect situation the player does not even notice that there are milestones, but simply progress in a way they like.
2) The way of a achieving the milestones should have a very low probability of halting the player. Meaning that the player should feel that they are not sure what they should do next.
The thing that are closest to what I want is to have something like main road the player can always travel forward on. This main road is then filled with side roads that the player can choose to detour too. I am actually not sure that this might actually be the way to do it
I just feel that it would take away the sense of exploration, by always forcing the player through a pre-designed route. Instead I want the player to feel as much as possible that they personally discover the things.
So just to state it outright: The biggest challenge is coming up with the condition for reaching a milestone, and not really the design of the milestone itself. Eg, the problem is to figure out what makes the conveyor belt to start and to figure out conveyor belt in the first place.
If you haven't done so already I'd suggest you make a little list of the reasons why you need these milestones and then check if there's other solutions. Maybe there's a better solution.
Perhaps I should not give up the thoughts of leaving everything totally open just yet. I just have a hard to time figuring out how to plan the basic plot points or having the player accidentally stumbling across the ending.
what if it's fun to get stuck? Maybe the problem could be turned into its own solution.
This is interesting, because a way to bypass is to make the stuck state more interesting, perhaps even rewarding. In most games getting stuck comes with large negative feedback (as all fun stuff suddenly stuck). But what if getting stuck would provide extra experience in some way? Of course, one can not provide endless extra content for stuck players, but it is a interesting way to think about it.
An alternative to this would be to simply require that the player does 5 things (out of a given 10 e.g.). It doesn't matter which 5 things.
This sort of design thinking can probably eliminate a lot of the chance to get stuck. On does not have to say in advance that only 5 was required either and make the player believe that they did as much as they could.