$product->get_categories() won't work because it's a woocommerce function, that basically is just a wrapper for
get_the_term_list, which has no sorting parameter. It's always good to take a look at the source to know what you're dealing with.
get_the_terms, but it also has no sorting parameter. The latter get the terms either from the cache
get_object_term_cache or directly
wp_get_object_terms. The cache is most likely of no use, because the terms there are saved with the wrong sorting, hence the problem you're having.
wp_get_object_terms on the other hand has - finally - the ability to define sorting.
From the codex:
wp_get_object_terms( $object_ids, $taxonomies, $args )
$args = array('orderby' => 'name', 'order' => 'ASC', 'fields' => 'all');
The first argument is called 'orderby' and has the default value of 'name'. Other supported values include 'count', 'slug', 'term_group', 'term_order', and 'term_id'.
The second argument is called 'order' and has the default value of 'ASC'. The only other value that will be acceptable is 'DESC'.
So this could get you closer to what you want, but take a look yourself.
Thirdly, you could just use
get_ancestors, which gives you back an
Array of ancestors from lowest to highest in the hierarchy
Which works fine on the woocommerce product category taxonomy as it is hierarchical. It gets a little bit problematic though if you're assigning multiple terms per hierarchy level. I've wrote an answer concerning this general topic, maybe it'll help you further.