Well I always did everything before entering, with the capability of defeating the final boss, and I had to flee from most of the random encounters. You pretty much need to do most of the side quests, unless you grossly overlevel, but I'd go for a bit of a story and something new over random encounters any day.