The evidence of Vice City police brutality firstly is that of the Torture Cells in the Vice City Police Department. This includes windows covered in blood and bloodied clothes hanging from hooks in the room. This could mean that the police brutally torture some of their prisoners to get information. The department of Washington Beach is considered to be the staple conspirators behind the act.
A second piece of evidence is that the police in the game doesn't arrest criminals (except Tommy Vercetti), they just beat them up, killing them in-game, and leave them until they either despawn, or are revived by paramedics. Evidence of this can be seen at 11:10 in the video below.