This is where Castlevania II: Simon's Quest really shines. Simon is not bound by a linear story line or by a castle. In Simon's Quest Simon can travel from town to town, cemetery to castle collecting the items he needs. Also, there are churches where you can sleep and you can purchase items from merchants. You also gain experience as you play by collecting hearts (Zelda, anyone?). This adds a very RPG like element to the game play that was absent in the first game.
Not only is the game non linear, it also features a cool switch from day to night every few minutes or so. During the day enemies are easier to kill and the towns are full of people (all of whom are medieval monks for some reason), but at night the zombies, skeletons and mummies come out (and are harder to kill).
My one issue with the game (besides Simon's horrible taste in fashion) is how much harder Simon's Quest is from the first one. I'm not sure if the controls are less responsive or if I'm just bad at it, but it is annoying.