As best as I can see, units heal ONLY in a city??!! I tried leaving them for a turn at an inn, but no healing.
Certainly an interesting design decision.
I think as long as your units don't move they'll heal, or maybe it has to be in your territory. Whatever it is, it sucks IMO.
Your units and sov heal slower than it takes your civilization to research, learn spells, build buildings/units, etc. It's kinda silly.
If you use any magic to heal your units then you'll be sitting around clicking to regain mana at 1pt/turn which is no better or is even worse.