I think my first brush with Castlevania was probably playing Super Castlevania in a shop(Dixons) when I was a wee lad. I made a few feeble attempts to clear the first level, but obviously in a shop it's only a matter of time before the staff drive you out.
My first proper Castlevania, as in one that I got to sit down and play the whole way through was Symphony of the Night which made me an immediate fan of the series, though I don't remember if the next game I played was Circle of the Moon or Castlevania Chronicles. I was disappointed by Chronicle initially, which was purely my own fault because I bought it without reading the back of the box. I had expected a compilation of old games, but it was actually just one old game re-released, and I was disappointed that Simon lacked much in the range of moves. However, once I really gave the game a bash, I found it to be a solid and engaging old school challenge.
Circle of the Moon was a good game I thought, though a tad hard and it really was a bugger to see the screen half the time on the old GameBoy Advance, and I liked the other Metroidvania games that came out though I thought they suffered from the law of diminishing returns.
I've since gone back and played some of the older Castlevanias though emulation. Super Castlevania IV was great I thought, though it got off to a slow start, and Rondo of Blood didn't do much for me. I've been intent on giving the old Nes games a bash though, as well as the Megadrive Bloodlines game.