Ack, so for approach 2. it looks like I just needed a deeper understanding of the $term variable:
$vid = 2; /* <---- put correct vocabulary ID here */
$terms = taxonomy_get_tree($vid);
print "<ul>";
foreach ( $terms as $term ) {
$tcount = taxonomy_term_count_nodes($term->tid);
print "<li>".
l($term->name,'taxonomy/term/'.$term->tid, array('title' => $tcount." products in ".$term->name)).
print "</li>";
} /* end foreach */
print "</ul>";It looks like I can play with that to create a menu based on the $term->depth
Is this the best way to accomplish what I want?