Hmm. Dastardly, I think Faery Tale Adventure is just right. It's quite huge and the atmosphere is creepy, just the kind of 16 bit world I like to get lost in!
Damn, Bamiga beat me to it, and even used "atmosphere" in his post. I guess we both agree the game is unique like that!