I really think that where to start depends on the type of game you prefer - a platformer where you go to the end of a stage (Mario, Mega Man, etc) or a Metroid style game where you go all over and have constant backtracking, RPG elements, powerups etc. Or...the 3D stlye games like Mario 64, Shadow of the Colossus and God of War.
The NES and SNES Castlevanias are stage based, 3 lives, continues, etc. Super CV IV on the SNES is often hailed as the best.
The other type is typically on handheld games, and those are lovingly nicknamed Metroid-Vanias, due to the game play similarities of Metroid. The whole game takes place in a castle area, with lots of rooms, sewers, floors, towers, etc. These have a lot of backtracking and leveling up. They also involve saving, as usually one death and game over. Symphony of the Night for the PSone is the undisputed king of this genre, and the first one in this style.
The 3rd style is the 3D games. These are the N64, PS2/Xbox/PS3/360 titles. These...vary in quality. The N64 ones are a little difficult to get the hang of, as they were very early in 3D tech. And some of the PS2 titles are just boring. If you like this route, I'd recommend either Curse of Darkness for PS2 or Lords of Shadow for PS3/360. These seem to be the most fulfilling titles. Just be warned, Lords of Shadows is like God of War with a whip. If you don't like GoW or DMC, then these probably aren't the titles for you,
My personal faves:
Platformers:
1: Super Castlevania IV (SNES)
2: Castlevania Bloodlines (Genesis)
3: Castlevania 1 (NES)
4: Castlevania 2 (NES - RPG like, not stage based)
5: Castlevania 3 (NES) - This one is HARD
RPG/Metroid-Vania
1: Symphony of the Night (PS1, PSP, PSN, XBlive) Probably the best in the series IMO
2: The DS/GBA ones all feel the same to me
3D/God of War style
1: Lords of Shadow (PS3, 360)
2: Curse of Darkness (PS2, Xbox)
the N64 titles are pretty bad, I love them...but i grew up with them. They are frustrating and the camera is terrible. But if you like a challenge, go for it...but don't judge the series based on these. I'd say play any of the NES/SNES and PSone games before you judge the series as a whole