You have to go a little bit in the story at first to get the steed and to be able to get levels, but after that you can pretty much do what you want. (Think you have to find 3 sites of grace to have that person come to you) I've mainly just wandered around for the first few days myself. 