In what circumstances do passengers or flight attendants have to take their shoes off?
Passengers are usually asked to remove their high-heeled shoes during an emergency evacuation as they may damage the slide. In other cases, it is better to leave the shoes on during emergency as once you are outside, you're worse off without them. The usual policy is to remove only the high-heeled shoes. For example, FAA says:


  FAA Policy. The FAA believes that the proper procedure regarding shoes during an aircraft evacuation is to leave them on. In the case of a forewarned evacuation it is desirable to remove high-heeled shoes and stow them in an approved stowage area such as an overhead bin. They should not be placed in the seat pocket.


This was the result of cases where the passengers sustained injuries while evacuating as they wore no shoes. For example, during the crash of Southern Airways Flight 242, the NTSB noted:


  The feet of a number of the survivors were cut and some were also burned because they had no shoes for protection. In accordance with standard evacuation procedures, the flight attendants had briefed the passengers to remove their shoes to prevent damage to evacuation slides.
  
  Had pillows and blankets been distributed and had shoes been worn, some of the passengers' injuries probably would have been less severe and more passengers probably would have been able to escape from the wreckage.


As for removing the shoes during flight, some regulatory authorities are against it, like the Australian Civil Aviation Safety Authority:


  The most common injuries to feet during accidents or emergencies can be prevented by wearing suitable footwear. ... Avoid sandals and high heeled dress shoes. Keep your footwear on during the flight.... High heeled dress shoes will have to be removed before using the escape slide.


As are some airlines, like the American Airlines:


  American may refuse to transport you, or may remove you from your flight at any point, for one or several reasons, including but not limited to:
  
  ...
  
  
  Are clothed in a manner that would cause discomfort or offense to other passengers or are barefoot.
  


I understand that there was an old rule to this effect, at least in US. Having the shoes on and taking them off both have their advantages and disadvantages. Except when challenged by a FA, I guess you can have/remove your shoes as you like (As long as the one sitting next isn't complaining). If the cabin crew asks though, its better to comply.

As far as the cabin crew is concerned, I'm not aware of any rule which says when they have to remove their shoes, so I guess its upto them, though it would be better for them to leave it on so as to take care of any sudden requirements. IATA recommends shoes which won't come off easily:


  Cabin Crew Uniforms
  
  ... The  following  is  intended  to  serve  as  a  guideline  for airlines
  when selecting new uniforms for their cabin crew:
  
  
  Shoes or boots should be flat or low-heeled and closed with laces or traps so that they will not be lost or thrown off;
  


Interestingly, this forum indicates that some airlines (including Aeroflot) require their FAs to wear high heels outside aircraft, which are changed to slip-ons (or other manageable ones) once in aircraft. From a news article:


  ... female flight attendants working for one of the world’s largest carriers, United Airlines, are required to wear shoes with a heel height of between one and three inches. Women crew members can only switch to a lower heel—it still has to be at least one-fourth of an inch high—during the service portion of the flight. ... Female attendants then have to switch back to the higher heels once the flight begins its initial descent.