So put this on for the first time today, and everyone is saying, basically, go kill the wizard. So I went right to the tower area, thinking I don't need to go elsewhere. But after seeing some walkthroughs, apparently you're supposed to go to the other locations first? I don't know how you're supposed to know this, but does this mean I have to start over? (I'm not very far, just outside of the tower right now)

Why don't you just go elsewhere? You can freely move between the locations.

You don't have to start over. Just keep exploring, go to the other areas on the map.