Buildings that change strat-map appearance (palace, roads, farms, walls) cannot be destroyed without causing a bug.

Once a city gets to a level, there is no way in making decrease in level or change the cultural appearance of the town while keeping it the same level.

If your towns are Large Towns, get them to 6,000 population and you'll be able to upgrade them to Minor City.