One key difference might be enabled systemd-resolved by default in
Fedora 34, but it is not in RHEL9. I think it should not be related
directly. But could it?

What does hostnamectl report after installation? What it thinks the
hostname is? Would the behaviour change if you disable systemd-resolved
and reboot?

I just did a fresh kickstart of F35 Server. I didn't do anything to set the hostname during installation. 

At first boot, I could see that the hostname was set to the reverse DNS-provided hostname "hostxxx.tc.camerontech.com" - this is normal and expected.

When I log in via ssh or on the KVM console, the hostname is hostxxx.tc.camerontech.com UNITL I REBOOT.

Once I reboot, the hostname is set up "fedora" with no FQDN. I am assuming it's somehow being set because of the lines in /etc/profile where the hostname is set, but I'm not sure.

I looked at the hostname-mode option of NetworkManger.conf, but I've tried various settings and it doesn't seem to work. From the man page:

hostname-mode
  Set the management mode of the hostname. This parameter will affect
  only the transient hostname. If a valid static hostname is set,
  NetworkManager will skip the update of the hostname despite the
  value of this option. An hostname empty or equal to 'localhost',
  'localhost6', 'localhost.localdomain' or 'localhost6.localdomain'
  is considered invalid.

  default: NetworkManager will update the hostname with the one
  provided via DHCP or reverse DNS lookup of the IP address on the
  connection with the default route or on any connection with the
  property hostname.only-from-default set to 'false'. Connections are
  considered in order of increasing value of the hostname.priority
  property. In case multiple connections have the same priority,
  connections activated earlier are considered first. If no hostname
  can be determined in such way, the hostname will be updated to the
  last one set outside NetworkManager or to 'localhost.localdomain'.

  dhcp: this is similar to 'default', with the difference that after
  trying to get the DHCP hostname, reverse DNS lookup is not done.
  Note that selecting this option is equivalent to setting the
  property 'hostname.from-dns-lookup' to 'false' globally for all
  connections in NetworkManager.conf.

  none: NetworkManager will not manage the transient hostname and
  will never set it.

I've set the hostname-mode to "default" in the NetworkManager.conf file and rebooted but it doesn't make any difference.

Here are screenshots: https://imgur.com/a/gRzswnI

Thomas