[Old Pedant]

Your HTML there is ILLEGAL. You have no </tr> to match each <tr>.

Anyway, I don't use PHP, but I don't see why you couldn't have at least tried my query. The transformation of your code to use it iis nearly trivial.

<?php

$sql = "
    SELECT L.lowest, E.*
    FROM expedia AS E,
         ( SELECT tag, MIN(price) AS lowest
           FROM expedia
           GROUP BY tag ) AS L
    WHERE E.tag = L.tag
    ORDER BY E.tag, E.price"; // change ORDER BY if you wish

$result = mysql_query( $sql ) or die( mysql_error() );

$rownumber = 0;
while( $rows = mysql_fetch_array($result) ) 
{
    ++$rownumber;

    $lowest = "$" . $rows["lowest"];
    $leg1   = $rows["leg1"];
    $leg2   = $rows["leg2"];
    $tag    = $rows["tag"];
    $url    = $rows["url"];
    $price  = $rows["price"];
   
    $ttl = "Lowest Price is $lowest for $leg1 - $leg2 with Search Tag : $tag";
?>
<tr title="<?echo $ttl;?>">
    <td align="center"><?echo $rownumber ?></td>
    <td align='center' border='1' frame="box" rules="all"><? echo $tag; ?></td>
    <td align='center' border='1' frame="box" rules="all"><? echo $url; ?></td>
    <td align='center' border='1' frame="box" rules="all"><? echo $price; ?></td>
</tr>
<?php
}
mysql_free_result($result);
mysql_close();
?>
</table>