Código PHP:
//Yo hice algo bastante óptimo es lo siguiente:
$sSQL ="SELECT id FROM tabla LIMIT 30";
/*Por ejemplo con un limite de 30 y el ORDER BY podria ayudar*/
$rs = mysql_query($sSQL);
while($row = mysql_fetch_array($rs)){
$array_values[] = $row["id"];
}
//hay una funcion de php que te devuelve una posion al azar de un array
$random_id = array_rand($array_values);
//entonces ahora solo hago un select de este valor,
$sSql ="SELECT * FROM tabla WHERE id=".$random_id;
....