Don't understand how much voodoo there is when specifying the Guest OS when setting up a new VM. Does giving the right answer really matter? Is it just a kind of documentation, or does it result in subtle differences in the configuration of the VM not otherwise visible unless you dig deeply into the VM's Advanced Configuration options?
In short should I select RHEL4, because it's closest, or Other Linux, because it's none of the above, or does it not really matter?
Go with other Linux as the RHEL4 will provide stuff specific to the 2.4 kernel.
I had minimal problems getting CentOS 5 up and running with Tools installed, just be sure you grab the Kernel-devel package to match the running kernal and you should be good.
Well RHEL4 is kernel 2.6.9 based but your point still stands, The "other 2.6 based Linux" would be the best choice since a number of things have changed between RHEL4 (2.6.9 kernel) and RHEL5 (2.6.18 kernel).