Portrait Of Ruin and Circle Of The Moon are really good.

Is their an overall story connecting all the games?

^Yea the stories do connect. http://castlevania.classicgaming.gamespy.com/storyline.html
That's my Castlevnia Bible :-)

Definitely start with Castlevania IV of Snes, if you have Wii download it. Why? Is it challenging but not too much like the Nes version, which is good for starters. The music, the game, all is fantastic and fun. With the Nes version you'd probably hate it, the first one is difficult because of control issues, the second one is easy to get lost, the third one is a good as a second option.

The DS are good but similar to Metroid and will take more time. Get Castlevania IV, you won't regret it, and if you do skip the Nes versions and play Dawn of Sorrow on DS.

No, you're not the only one. That game was awesome!

The GBA and DS-games are definitely worth your while, and I personally love the PS2-games as well. Symphony of the Night is, as someone else in this thread said, the high point of the series. Great game indeed.