You really need to use the early turns when the Overlord is still in the fortress to build up food supply. Remember that you can build new farms in ocean shallows as well, you want to expand out in more than one direction, and really try to get a good supply of food being run from multiple angles so that Demonica can't just easily wipe it out in one turn. Basically early game, just sit on every farm/factory you can while steadily growing survivors. The more you move people, the more you waste turns that could be used resource gathering. I tend to sit skirmishers or scouts on resource buildings, and use soldiers (or skirmishers) if I need to protect them from monsters.
While spreading out, you need to really expand your survivor count, not faster than you can grow food, but fast enough that you can do everything you need. Remember more survivors means eating more food, but it also means more farms/clinics/factories you can man.
The special tile abilities can be really helpful as well, if one of your farms is about to fall, ring a swamp tower on the opposite side of the map to draw Demonica away. The structure that lets you recruit survivors the same turn as movement is also really helpful for expanding your base. The amplify towers/pyramids are also really great for expanding your border, or stalling demonica which gives you time to gather more resource.
The best way to deal with outposts/deep gates is honestly to avoid them if possible (careful of using an amplify tower if deep gates are around). If you absolutely can't avoid it, then I would use multiple units so they can cover each other, and even build forts/housing if needed. Soldiers are really great for this as they have a nice pool of health. Having multiple clinics also helps.
Basically the short version. Know what tiles you can build what on. Use the special ability tiles. Keep people on factories/clinics/farms as long as you can and spread them out. Use dedicated soldiers/skirmishers for recruiting, bashing towers, etc. Also kill monsters as soon as you can so they don't build up.
Good luck! The trick is really, build a strong powerbase early and then you have some wiggle room - but don't get too lax with it.
Edit: If its getting to the point of frustrating, don't be afraid of turning it down either. That's what difficulties are for!
