At the time, they were some of the best graphics I remember seeing, especially on the N64. OoT had a wonderful pallet of colours, some great textures, and despite looking a bit blocky, still did a great job with polygon constructed characters.
Now, looking back on those graphics, they don't hold up to the graphics of today, but neither does any older game as such. Regardless, they are still fairly impressive.
I don't replay OoT and think about how horrid the graphics are in terms of being dated. Whether that's in part due to the fact that the story and gameplay overshadow the graphics by pulling you into the world, I don't know, but they must be good if within 5 minutes, you're not thinking about how dated the game looks.