Every single encounter means death if you cant outrun them,to reach the two locations on map you encounter guys with machine guns in power armor, the equivalent of deathclaws, and anyway when you arrive you get shot by more guys in power armor while you have absolutely no gear . Oh meet a guy fighting ant, help him then he turns against you to steal your shit The other location you are irradiated and need to melee dogs and rats with bare hands and its not going much better. Maybe its all an elaborate russian joke.
Dude, it's like you've never played Fallout before. With high AG (and there's not reason to have less than 10) you can outrun any enemy and escape; with Stealth it's much easier. Or invest in Outdoorsman and have a high chance of skipping random encounter. If you play melee build you don't have to deal with the weapon problem; have high AG and Stealth as of above, get close and kick the shit out of them. With firearms builds it's little bit more complicated since I really don't know where you can get the legit first gun (I stole SMG from the guard who kicks your ass in Tartarus, served me a long time, great exploit), but anyway - strive for sniping or high-crit burst offense and you will be fine. 10 AG and high Stealth help in every Fallout game.
As of PA dudes, they are local equivalent of Fallout 2 Enlcave patrols. Stay away from the Olympus building - it's endgame location and PA patrols do spawn there.