On the original NES -
There was this funny fantasy-type game called Rygar. I loved it. lol. Also remember having fun wtih Goonies. But all-time favorite NES Fantasy game was Faxanadu.
Super Pitfall, converted to NES, was pretty damn hard - but I liked it a lot and spent so many countless hours getting frustrated and trying to beat the darn thing. It was nearly impossible with an insane amount of things to do and only being able to get hit 3 times before death. lol.