Fez is pretty poppy and could (probably) be done in RGB222 with some concessions, whereas something like Spelunky would have a harder time.
You're right .. although Fez actually ( secretly ) has allot of color nuances, which don't easily translate to for example the Master System. Here's a quick conversion attempt nevertheless.
.. using the following palette ..
Obviously, you would get better results creating / redoing the graphics for a platform specifically compared to a conversion.
And just for the heck of it, Spelunky on MegaDrive ( using a separate layer for the background )