Based on ISO short-wavelength spectrograph (SWS)+long-wavelength spectrograph (LWS) observations, IRAS 16594-4656 is identified as a new member of the rare class of C-rich proto-planetary nebulae with the 21 μm dust feature in emission. In addition, the major polycyclic aromatic hydrocarbon (PAH) emission bands at 3.3, 6.2, 7.7, 8.6, and 11.3 μm are detected, together with unusually strong features at 12.6 and 13.4 mum, very rarely observed, attributed to PAH species with a high degree of hydrogenation. The shapes and relative intensities of the various features found are consistent with a mixed population of transient decomposition products of large hydrogenated amorphous carbonaceous (HAC) grains, consisting of fullerenes with different degrees of hydrogenation, which we suggest to be the main carriers of the strong 21 μm feature, and a combination of small and large partially dehydrogenated cationic PAH molecules excited by the visible radiation coming from the central star. Additional features corresponding to crystalline silicates (mostly pyroxenes) are also tentatively detected, together with a possible very broad unidentified emission feature centered around 30 mum, previously reported as appearing in combination with the 21 μm feature in other proto-planetary nebulae candidates. The combination of features corresponding to O-rich and C-rich dust grains, if real, would suggest a recent change to a C-rich chemistry in the outer envelope of IRAS 16594-4656. With the help of optical ground-based spectroscopy and recently obtained Hubble Space Telescope (HST) images, we identify IRAS 16594-4656 as a new transition object between the asymptotic giant branch (post-AGB) and the planetary nebula (PN) stage. The ground-based optical spectrum shows only the Balmer lines in emission and a faint, probably shock-excited, [O I] emission over a very red continuum where strong, probably circumstellar, diffuse interstellar absorption bands (DIBs) at 5780 and 6281-6284 Å are clearly seen. HST WFPC2 continuum images reveal the presence of a bright central star surrounded by a bipolar reflection nebula with a multiple-axis morphology and a maximum size of ~5^''x11^''.