I had the same problem, but Fawkes goes to Underworld after a time, so if you can’t find him in the citadel look there.
Yeah, the Overlords are tough. I play on very hard, and the only way I can take them out is reverse pickpocketing a plasma grenade into their gear, or, I use the firelance. Anything else is pure suicide.
The trailer for the next DLC this month is out, and it looks good. Then in August, there is supposed to be one more.
Oh, and have you run into the albino radscorpions? Those guys are a pain as well.