Firstly, $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.
Secondly,get_the_term_list uses 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:
Usage
wp_get_object_terms( $object_ids, $taxonomies, $args )
Default Arguments
$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.