How does the choice of metal (oxide) catalyst affect the range of unsaturated compounds that can be hydrogenated?
The currently accepted hydrogenation mechanism for metal like palladium is the Horiuti-Polanyi mechanism. (image)  This mechanism works with good yield for alkenes and alkynes.  For an aromatic compound, the activation energy is much higher because the aromaticity of the target molecule is being broken by the first hydrogenation.  Indeed, 1,3-cyclohexadiene is very unstable and will revert to benzene and hydrogen instead of continuing to cyclohexane.  

Addition of a Lewis Acid makes palladium an acceptable catalyst for the hydrogenation of benzene, however.  An intermediate compound with the benzene and the LA is first formed, and hydrogen is added to this intermediate.  This paper discusses the mechanism of hydrogenation in the presence of a Lewis Acid.  

Rhodium catalysts work slightly differently.  They generally have ligands attached that help stabilize the intermediates.  You can see a simplified mechanism here and there are papers discussing specific catalysts here and here.  Basically, in the case of benzene, the relatively unstable 1,2-cyclohexadiene is held in place on the catalyst until it has been completely hydrogenated.