Repita los resultados según la categoría, pero solo muestra la categoría una vez

Como ya está ordenando su resultado por producto, podría hacer algo como esto:

$currentProduct = null;

foreach($products as $product) {

    if ($currentProduct != $product['product']) {
        // We got a new product. Show it with some fancy html
        // Then store it in $currentProduct for the next iteration 
        $currentProduct = $product['product'];
    }

    // Show the title with some fancy html
}

Si desea utilizar su do while existente -bucle en cambio, es lo mismo.