[QUOTE=Edward M]The Third category is 3d Castlevanias. These are the ones for PS2 and N64. You should probably avoid these.[/QUOTE]
I personally think the 3D Castlevanias are action-platformers just like the 2D ones in Ed's first category, just that they are in 3D. I personally like the N64 games, Castlevania 64 and Legacy of Darkness, even though they have some wicked camera issues. The pacing and story and just sheer atmosphere of those games was fantastic. I don't think the other two 3D Castlevanias, Lament of Innocence and Curse of Darkness, are all that interesting though.Given how dedicated you are, Atarifever, old-style games, I would suggest the original Castlevania, Castlevania 3: Dracula's Curse, or Super Castlevania IV. However, given that you preferred Genesis and Sega in general to the NES and SNES, there's also Castlevania: Bloodlines for the Genesis.
I also believe that you of all people might appreciate Castlevania II: Simon's Quest on the NES. It was more RPG-like, and a precursor to the Metroidvania style to come in Symphony of the Night and later, than its action-platformer predescessor.
Other than that, you are a DS owner right? Both of the Castlevania games available on the DS are suitable for you. Dawn of Sorrow is along the lines of the Metroidvania style (just like its direct GBA prequel, Aria of Sorrow), and Portrait of Ruin is very enjoyable and a better visual experience itself.
Now mind you -- two of the greatest Castlevania games of all time among fans, Rondo of Blood and Symphony of the Night, are coming out for the PSP. They are directly linked to each other, as SOTN is a direct sequel to ROB, and they are both celebrated. It will mark the first of the two's release in the US, actually, one we've all been long waiting for. But take that as you will, as I wasn't sure you had a PSP.
It was certainly a very different game compared to the other Zeldas, but that didn't make it any less fun or great.