Super Mario 64, Noby Noby Boy and Tekken 5's Devil Within scared me a lot.
In Super Mario 64, Jolly Roger's Bay, Dire Dire Docks and Big Boo's Haunt had a bunch of creepy species like the eel, spellbooks, magic tomes, the merry-go-round trap and the hurricane. The metal box area in Hazy Maze cave has an exit which makes Mario fly out of the waterfall back to the castle grounds when failed.
Noby Noby Boy was a game with horrific, alien-like music and centers mainly on caterpillars. Really? Insects creep me out...
Devil Within had True Ogre as the last boss. I could not stand him spinning around too many times, but I at least found his weakness to grab his tail and spin throw right after landing from the flamethrower.