Вывод категорий и подкатегорий

Писать надо определенно один запрос. А если не один, то использовать подготовленные запросы и передавать параметры туда как следует.

PDO в принципе и сам умеет группировать, хот такая группировка и не очень функциональна. Ваш код будет выглядеть примерно так (не проверено):

$st = $dbh->query("SELECT c.id, c.name
                         ,s.id as sub_id, s.name as sub_name
                   FROM category AS c
                   LEFT JOIN sub_category AS s ON (s.category_id = c.id)");
$categories = $st->fetchAll(PDO::FETCH_ASSOC | PDO::FETCH_GROUP);
echo '<ul>';
foreach($categories as $cId => $data) {
    echo '<li>';
    echo '<a href="cat-'.$cId.'">'.$data[0]['name']. '</a>';
    echo '<ul>';
    foreach($data as $sub) {
        echo '<li><a href="sub-'.$sub['sub_id'].'">' . $sub['sub_name'] . '</a></li>';
    }
    echo '</ul>';
    echo '</li>';
}
echo '</ul>';

Но и самому такую группировку сделать весьма просто:
исходные

$data = [
        ['id' => 1, 'name' => 'Программы', 'sub_id' => 1, 'sub_name' => "Антивирусы"],
        ['id' => 1, 'name' => 'Программы', 'sub_id' => 2, 'sub_name' => "Запись"],
        ['id' => 1, 'name' => 'Программы', 'sub_id' => 3, 'sub_name' => "Интернет"],
        ['id' => 1, 'name' => 'Программы', 'sub_id' => 4, 'sub_name' => "Аудио"],
        ['id' => 2, 'name' => 'Фильмы',    'sub_id' => 5, 'sub_name' => "Боевики"],
        ['id' => 2, 'name' => 'Фильмы',    'sub_id' => 6, 'sub_name' => "Фантастика"],
        ['id' => 2, 'name' => 'Фильмы',    'sub_id' => 7, 'sub_name' => "Ужастики"]
    ];

группировка

$result = [];
$cId = null;
foreach($data as $d){
    if($d['id'] != $cId) {
        $cId = $d['id'];
        $result[$cId] = ['id' => $d['id'], 'name' => $d['name'], 'sub' => [] ];
    }
    $result[$cId]['sub'][] = ['id' => $d['sub_id'], 'name' => $d['sub_name']];
}
print_r($result);

Почти всегда лучше делать один запрос. Только в запросе не забыть про сортировку

$pdo = new PDO($dsn, $user, $pass, $opt);
$sql = "SELECT
    category.id, category.name,
    sub_category.id sub_id, sub_category.name sub_name
  FROM category LEFT JOIN sub_category
  ON sub_category.category_id = category.id
  ORDER BY sub_category.category_id";
$res = $pdo->query($sql)->fetchAll();
echo '<ul>';
$old_id = null;
foreach($res as $key => $val) {
  if ($val['id'] !== $old_id) {
    if (isset($old_id))
      echo '</ul></li>';
    $old_id = $val['id'];
    echo '<li>';
    echo '<a href="cat-'.$val['id'].'">'.$val['name']. '</a>';
    echo '<ul>';
  }
  if (isset($val['sub_id']))
    echo '<li><a href="sub-'.$val['sub_id'].'">' . $val['sub_name'] . '</a></li>';
}
if (isset($old_id))
  echo '</ul></li>';
echo '</ul>';

Ну и на будущее: писать SELECT * плохо всегда. Даже если Вам нужно выбрать 50 полей. Всегда указывайте имена нужных Вам полей