Executar uma consulta com base em várias caixas de seleção

O cerne do seu problema parece ser o fato de você estar cercando a coluna DetailName entre aspas simples:"'DetailName'='" quando tudo o que deveria ser é "DetailName='"

Em uma nota de segurança, gostaria de salientar que a função mysql_escape_string() você está usando para forçar a entrada a ser compatível com o mysql é antigo e cheio de falhas de segurança. Em vez disso, recomendo usar a implementação muito mais segura:mysql_real_escape_string() . Os exemplos de código abaixo fazem uso da função mais recente e segura.

No entanto, separado desses problemas, eu recomendaria uma abordagem um pouco diferente, que será mais fácil de ler e muito mais fácil de gerenciar a longo prazo.

Para começar, recomendo usar o mesmo nome em todas as caixas de seleção e usar DetailName como o valor e não como a chave:

<td>
    <input name="criteria[]" type="checkbox" id="Buffet" value="Buffet" />
    <strong><label for="Buffet">Buffet</label></strong>
</td>
<td>
    <input name="criteria[]" type="checkbox" id="Breakfast" value="Breakfast" />
    <strong><label for="Breakfast">Breakfast</label></strong>
</td>
<td>
    <input name="criteria[]" type="checkbox" id="BYOB" value="BYOB" />
    <strong><label for="BYOB">BYOB</label></strong>
</td>

Em seguida, usando os valores de suas entradas em vez das chaves, agora podemos gerar nossa cláusula. Muito eficiente:

// Runs mysql_real_escape_string() on every value encountered.
$clean_criteria = array_map('mysql_real_escape_string', $_REQUEST['criteria']);
// Convert the array into a string.
$criteria = implode("','", $clean_criteria);

Por fim, em sua consulta, recomendo usar o IN operador em vez do OR operador para eficiência e legibilidade:

SELECT
    tblLocations.CityID, tblRestaurants.RestName, tblLocations.Street, tblLocations.Phone, tblLocations.Price, tblLocations.Rating, tblDetails.DetailName
FROM
    (
        tblRestaurants
    INNER JOIN
        tblLocations ON tblRestaurants.RestID = tblLocations.RestID
    )            
INNER JOIN
    (
        tblLocDet
    INNER JOIN
        tblDetails ON tblLocDet.DetailID = tblDetails.DetailID
    ) ON tblLocations.LocationID = tblLocDet.LocID
WHERE tblLocations.CityID='16' AND tblDetails.DetailName IN ($criteria)
ORDER BY tblRestaurants.RestName ASC

Aqui está todo o lado PHP das coisas combinando as modificações que sugiro com sua lógica:

<?php
require "congig.php";
if(!empty($_POST['criteria'])) { // empty() checks if the value is set before checking if it's empty.
    foreach($_POST['criteria'] as $key=>$value){ 
        // Runs mysql_real_escape_string() on every value encountered.
        $clean_criteria = array_map('mysql_real_escape_string', $_REQUEST['criteria']);
        // Convert the array into a string.
        $criteria = implode("','", $clean_criteria);
    }

    $rs = mysql_query("
        SELECT
            tblLocations.CityID, tblRestaurants.RestName, tblLocations.Street, tblLocations.Phone, tblLocations.Price, tblLocations.Rating, tblDetails.DetailName
        FROM
            (
                tblRestaurants
            INNER JOIN
                tblLocations ON tblRestaurants.RestID = tblLocations.RestID
            )            
        INNER JOIN
            (
                tblLocDet
            INNER JOIN
                tblDetails ON tblLocDet.DetailID = tblDetails.DetailID
            ) ON tblLocations.LocationID = tblLocDet.LocID
        WHERE tblLocations.CityID='16' AND tblDetails.DetailName IN ($criteria)
        ORDER BY tblRestaurants.RestName ASC
    ");
    if(!$rs) {
        echo "Cannot parse query";
    } else if(mysql_num_rows($rs) == 0) {
        echo "No records found";
    } else {
        echo "<table id=\"myTable\" table width=\"710\" class=\"beautifuldata\" align=\"Left\" cellspacing=\"0\">\n";
        echo "<thead>\n<tr>";
        echo "<th>PLACE</th>";
        echo "<th>ADDRESS</th>";
        echo "<th>PHONE</th>";
        echo "<th>PRICE</th>";
        echo "<th>RATING</th>";
        echo "</tr>\n</thead>\n";
        while($row = mysql_fetch_array($rs)) {
            echo"<tr>
            <td><strong><a href='$row[RestPage]'>$row[RestName]</a></strong></td>
            <td>$row[Address]</td>
            <td>$row[Phone]</td>
            <td>$row[Price]</td>
            <td>$row[Rating]</td>
            </tr>\n";
        }
        echo "</table><br />\n";
    }
}