In three different locations in the water that surround the city, Washington Beach, Leaf Links, and Little Havana, two fat men wearing cement shoes can be seen underwater. The men are stripped of their clothes, except for their underwear. They are also slightly obese and appear to have been dead for not very long, because their skin hasn't been decomposed completely. They have their feet inside of dried cement and have been dumped into the ocean, which was a notorious method of torturing and killing people that the Mafia used in the 80s.
During the final mission, Keep Your Friends Close, Ken Rosenberg mentions that the Forelli Family are coming to fit him with some cement shoes. This seems to imply that the Mafia is responsible for this criminal act.
Vice City Mafia
The Cement Shoe Men is an Easter egg referencing the Mafia in Vice City. One of the Cement Shoe Men can be found north of 1102 Washington Street, across the water along the southwestern coast. The other is east of Skumole Shack, on the sea rock between Downtown and Leaf Links. This myth is closed and is said to be just an Easter egg.
The following section features information from NeoSeeker
These Cement Shoe Men can also be a reference to Jimmy Hoffa. Hoffa was a powerful and controversial leader of the Teamsters Union from 1957 to 1971. Often alleged to have ties to organized crime, Hoffa was finally convicted of fraud and jury tampering in 1964 and served four years. In 1975, while trying to regain power in the union, Hoffa disappeared from a restaurant parking lot in Bloomfield Hills, Michigan. He was widely assumed to have been killed by the Mafia. His body was never found, and in 1983, he was declared legally dead. In September of 2001, news reports claimed that DNA tests by the FBI had tied Hoffa to a car driven by his associate Charles O'Brien the day Hoffa went missing, suggesting that charges might still be brought in the case. Many believed Hoffa to be thrown into a cement mixer and mixed in with an architectural structure.
- The Forelli Family is often believed to be the leading culprits behind the Cement Shoe Men, due to their barbaric nature and vigorous mafia web. A stabbed man, who can be seen perceived at Marco's Bistro (Vice City Version), this act is similar to the Cement Shoe Men. This theory was later proved to be authentic (see above).
- One of the men in cement shoes is believed to be Diaz, due to his resemblance to him but this is unlikely since he is seen at the beginning of the game. Also, both men are exactly identical in appearance, making this impossible to be Diaz.
- A pedestrian that can be found in Ocean Beach, looks very similar to the Cement Shoe Men. This ped is believed to be the base for their models.