- Magic in Heroes 3

I would choose Earth. Although, if the city already has an Astral Gate and doesn't have a City Gate or Resurrection, I would think carefully and, depending on the difficulty and size of the map, I would choose either Air (if it's really needed) or Earth (if it can wait).
But in general, I would probably choose Air, because if the hero is at a level where only one slot is left, then probably many cities have already been captured; and if none of them have a City Gate or Resurrection, then it's not worth it.