The Tavern

Any tips for coping with an encounter with an unseen horror relatively early in the game... i.e. before I have the ability to see invisible, or any scrolls of fog?

Corona and Sticky Flame will reveal them.
Kill them with AOE like Fireball or Wands of Iceblast.
Mephitic Cloud will confuse them so you can get away.
They move similar to bats. So, retreat into a corridor, move one tile back, one tile forth to attack (if you can't see their outline).

As already said, unseen horrors have batty movement so for most char is easy to retreat to nearest corridor\staircase. Practice with a bat to learn how minimize its attack - but generally speaking the best route is move backwards in only one direction.

While in the corridor if you have some decent weapon and AC alternating 1 step back - to get him close to you - 1 attack with ctrl is usually enough to deal with them.
With ood horror as said aoe works fine - but try to not hit yourself - but also things like poly, disint, or any other hex - as they have poor MR.

If the char has no AC or HP they are extremely deadly: use fear, tele or whatever to run away from them asap.

If you are strong enough to melee with them but have no way to show their location then I find the easiest way is to go to a corridor and then repeatedly attack in place by holding ctrl plus a direction. It is much less effort than moving back and forth. But it can be dangerous if you don't have enough armor.

And if you want to do that but are not strong enough on your own to melee it, you can use a potion of lignification.

If you stand and swing at nothing with an axe, will the cleaving catch it if it's in any of the tiles around you or just the one you swing at?

Axe will hit it if it's in any of the tiles around you.

Stop playing octopodes.

With an axe, you can just stand there and point in a direction with Ctrl. ("Swing at nothing" yes if that isn't clear). Just as long as you have plenty of armor and HP. You'll catch it pretty soon if you have some skill.

You can also back along a corridor with a shaft and hope it follows and gets sucked down to the next level.

If you aren't on the verge of death, it can sometimes work to shoot in a possible direction with venom weapons or spells. You'll probably need more than one hit unless you have super-powered Venom Bolt or a giant weapon. But it can speed up the process if you guess correctly where they are, or if you can just fire a bolt along a one-tile corridor into them.