get categories the post was in and just been removed from

save_post runs too late to do what you are trying to do. That hook fires after the post and related meta data are stored. The category has already been removed at that point, and WordPress keeps no record.

You will need to hook into the save process earlier, perhaps pre_post_update:

add_action(
  'pre_post_update',
  function($post_ID,$data) {
    var_dump($post_ID,$data);
    var_dump(get_the_category($post_ID));
    die;
  },
  10,2
);

Proof of concept code only, obviously.