Well the reason I'm saying that you should have it from the start is because, it should be a viable city for the Arabs to conquer, because it would be quite cool, if you could one day have a crusade called to capture Palermo, or something like that.
And yes I do think London should be there from the start of the game, but more importantly I think there cities which flip to them should spawn at relatively the same time that the French do, and they should be heavily armed so that the French AI don't take is so easily. Plus I DON"T think its ok that Calais and Cherbourg are the cities that flip, instead it should be Rennes and Caen, these are the cities which have historic ties to the Norman crown. I don't know where you guys got Cherbourg and Calais from?