I believe if you customize the Flat Rate flat shipping module in:
/includes/modules/shipping/flat.php

you could customize it with the code in RED:
Code:
    function quote($method = '') {
      global $order;

// bof: custom calculate shipping
      global $db, $cart;
      // check how many from category 12 for $16.00 shipping
      $chk_cat16 = $_SESSION['cart']->in_cart_check('master_categories_id','12');
      // check how many from all categories for $8.00 shipping
      $chk_catall = $_SESSION['cart']->count_contents();
      $chk_customer_orders = $db->Execute("select orders_id from " . TABLE_ORDERS . " WHERE customers_id = '" . (int)$_SESSION['customer_id'] . "'");
      $current_shipping = 0.00;
      // charge 16.00 for category 12
      if ($chk_cat16 > 0) {
        $current_shipping += 16.00;
      }
      // charge $8.00 for all other categories
      if ($chk_catall > 0 && ($chk_catall != $chk_cat16)) {
        $current_shipping += 8.00;
      }
      // if this is first order and over $80.00
      if ($chk_customer_orders->RecordCount() == 0 && $_SESSION['cart']->show_total() > 80.00) {
        if ($chk_cat16 > 0) {
        // charge only $16.00 for shipping if from category 12
          $current_shipping = 16.00;
        } else {
        // Free Shipping if not category 12
          $current_shipping = 0.00;
        }
      }

      $this->quotes = array('id' => $this->code,
                            'module' => MODULE_SHIPPING_FLAT_TEXT_TITLE,
                            'methods' => array(array('id' => $this->code,
                                                     'title' => MODULE_SHIPPING_FLAT_TEXT_WAY,
                                                     'cost' => MODULE_SHIPPING_FLAT_COST + $current_shipping)));

// eof: custom calculate shipping
and it should do what you are asking for ...

This is example is using categories_12 12 as referenced by:
master_categories_id

check for Products using 12 as the master_categories_id ...