Right now, you could easily stumble upon underdark any time after the goblin fight at the grove gate. First playthrough, I didn't find Halsin. Didn't help the tieflings or the goblins. Found underdark and navigated past scary fights and found the boat that ends EA. Accidentally skipped most of the main story. The story could easily pick up from there as you find out these guys are messing with your parasite. There are also 2 others exits out of the EA area that we don't know how they will play out. I really wouldn't say the story forces you to follow it in the sequence it tells you about stuff. To me it seems like you can totally just go look around and should eventually find leads.
