You need at least 20 dex to make the advancement. If your going for a brawler then thats what your dex would be. If you go for gunslinger then your str should equal your level (I think).
As far as maps go, if you want to go straight into natilus port then wait outside of the gate east of henesys. Its below the portal that leads to ellania. I have mine waiting next to olaf to pick up the path of the pirate quest when its released.