We have played Medina several times these years and only now ran into these two questions:
1) It says that you must leave room between two wall pieces between different towers. A gate, so to speak. Does that mean that the space next to this gate can also not be blocked by a palace or stable? (We played it that you can 'block' the gate with a palace or stable piece. The stables and palace pieces do have little doors in them...)
Just the walls. The "gate" is there just to keep the walls separate and clear which is connected to which tower. The buildings don't care about the gate and so can block it.
2) It says that the first palace that is connected to a tower gets the tower bonus. Whether it is first claimed and later connected, or first connected and later claimed. The next palace that is connected by palace pieces to the tower AND is claimed AFTER it is connected then gets the bonus. OR you can connect an already claimed palace with a stable to the wall to get the bonus. (We played it that the last palace that is connected to the wall gets the bonus, whether it was first claimed and then connected or the other way around. This seems to be wrong.)
I don't think it matters. It is the first to have a claimed building connected to that tower via a wall.