Haz un shuffle()
www.php.net/shuffle del array $array_values . Luego en la consulta vas a usar IN
www.mysql.com/IN , asi que tienes que crear con implode()
www.php.net/implode la cadena a partir de $array_values .
Código PHP:
$sSQL ="SELECT user_id FROM usuarios WHERE estilo1_usuario='".$estilo."' OR estilo2_usuario='".$estilo."' LIMIT 5";
$rs = mysql_query($sSQL);
while($row = mysql_fetch_array($rs)){
$array_values[] = $row["user_id"];
}
shuffle($array_values);
$texto_in=implode(',',$array_values);
$sSql=mysql_query("SELECT * FROM usuarios WHERE user_id IN (".$texto_in.")");
while ($row = mysql_fetch_array($sSql))
{
echo "
<tr><td style='padding-top:2px; padding-bottom:2px; padding-left:2px; border-bottom: solid 1px #9C9C9C;' class='c'>
<img src='imagenes/arrow.png'> <a href='index.php?a=perfil&id=".$row['user_id']."' style='font-size:11px;'>".$row['user_name']."</a>
</td></tr>
";
}