Do we upgrade core or PHP first? We have Drupal 7 running on PHP 5.6. Do we upgrade to PHP 7 first, or do we first upgrade Drupal?
Drupal 7 can run on any PHP version between PHP 5.6 and PHP 7.3. For running on PHP 7.4, it's required at least Drupal 7.71.
Drupal 8 can run on any PHP version that is newer than PHP 5.6. For running on PHP 7.4, it's required at least Drupal 8.8.3.
If the site is running a version of Drupal that is older than Drupal 7.71, I would first upgrade PHP to PHP 7.3, and then upgrade to Drupal 8.
If the site is running on Drupal 7.71 or any newer version, you can upgrade to PHP 7.4, if you mean to upgrade Drupal to Drupal 8.8.3 or a newer version.
I would also test the upgrade on a local test site, as third-party modules you are using could cause problems with newer PHP versions.
It should be safer to upgrade to PHP 7.3, as there are backward incompatible changes in PHP 7.4 that required changing the code in Drupal 7; it's probable the same changes are required in third-party modules, but those changes are still to be applied to those modules.