Can I find the term depth via $node without resorting to a taxonomy_get_tree or an SQL query?
The data for taxonomy is in the database. If you want to get that data there is no way to do so without running a database query.

Any function that retrieves this data (including taxonomy_get_tree() and the function you link to above) has to run database queries to get at the data.

taxonomy_get_tree() is a bit heavy so I'd advise using the term_depth function you link to. If you want to increase performance slightly you can improve that function to offer a static page load cache. This will only make a difference if you call the function more than once in a single page load though:

function term_depth($tid) {
  static $depths = array();

  if (!isset($depths[$tid])) {
    $parent = db_result(db_query("SELECT parent FROM {term_hierarchy} WHERE tid = %d", $tid));
    if ($parent == 0) {
      $depths[$tid] = 1;
    }
    else {
      $depths[$tid] = 1 + term_depth($parent);
    }
  }

  return $depths[$tid];
}


Short of building your own cache mechanism that doesn't rely on the database (which would be a massive amount of overkill for this situation) I don't see any way of making this more performant.