I must be thinking of a different game then, cuz I swear there's a game on the NES where a normal-sized hero and a fairy-sized fairy are implied to have a romance. I might be thinking of Landstalker on the Genesis, but why I'd be confusing that with an NES side-scroller is anybody's guess.