Why start with a random religion? The starting religion of the city should represent the religion of the city's first inhabitants, its founders, the settlers.
I guess I am ok with there not being a 100% chance of it spreading there, but I don't like the random religion idea.
Some settlers do leave their homeland for religious freedom, but most carry their beliefs with them. These beliefs may or may not conform to the norms of their motherland. I would like to point out, again, that it doesn't really matter what the religion of the state is, what matters is the religion of the settlers.
Since many people don't continue follow the faiths they were raised in, I think that there should be a chance for religions to disappear from a city or unit on their own. I would rather have a higher spread chance and a disappearance chance to counter it.
I would also like it if units with religious promotions had a slight chance of spreading their religion both to other units on their same tile and to the cities in which they are garrisoned. It might also be nice if irreligious units of agnostic leaders had a similar chance to remove religions.
These too make much more sense historically, but I'm not insisting the changes be made.