Castlevania is traditionally split into two camps when it comes to 2D Castlevania games, though there is some overlap. Classicvania and Metroidvania. If you like SotN because it's like Metroid with lots of exploration and RPG elements, then you will lean toward the games made post-2000. From my experience, SotN is probably the best of the Metroidvanias overall.
Meanwhile, Classicvania's equivalent of SotN is arguably Super Castlevania IV.
There's not a lot of games Castlevania fans can all agree on, but I'd say somewhere around 90% would say that SotN, Super Castlevania IV, and Castlevania III: Dracula's Curse are must-plays. (While I have mixed feelings about it, a lot of fans like Rondo of Blood a lot, too, which is the prequel to SotN, and marks a transition between gameplay styles).
Here's a quick, messy rundown of the series to give you an idea of where to start. (For kicks, I'll end each with my
personal general gut reaction rating of 1-4 stars in terms of enjoyment, AND I'll
UNDERLINE the ones that fans tend to like the most. PLUS, since you like graphics, I'll highlight in
red the ones that people like to look at the most in terms of 2D).
NES:Castlevania - Classic linear action-platforming game. ***
Simon's Quest - A proto-SotN that features explorable mansions and towns, and collectable items. ***
Dracula's Curse - One of the most ambitious Castlevania games, combining classic linear action-platforming with 4 playable characters (swap between two on-the-fly at any time after a certain stage) and tons of branching paths between levels throughout the game. ****
GameBoy:The Adventure - Classic linear action-platforming game with really challenging controls and game design. ***
Belmont's Revenge - Classic linear action-platforming game that smooths out the wrinkles of The Adventure and adds a Megaman-type stage select that allows you to choose your path through the game. ****
Legends - Classic linear action-platforming game that's rather bland and clunky; though it stars one of the series' few female heroes. *
SNES:Super Castlevania IV - Classic linear action-platforming game with a lot of dynamic gameplay and visuals. ****
Dracula X - Classic linear action-platforming game with a few branching paths and side missions of saving prisoners. (It is a reimagining of Rondo of Blood, but a unique game in its own right). ****
PC Engine/Wii Virtual Console/PSP:Rondo of Blood - Classic linear action-platforming game with a lot of in-level branching paths. (There is a 2.5D remake for PSP). ***
Sega Genesis:Castlevania Bloodlines - Classic linear action-platforming game with two characters and some interesting quirks reminiscent of Castlevania IV. ****
Wii Ware:The Adventure Rebirth - Classic linear action-platforming game with some branching paths restricted to each level. ****
Sharp X68000/PS1:Castlevania Chronicles - Classic linear action-platforming game. ** (PS1 version has a update remake).
PS1:SotN - Classic Metroidvania that changed the series. ***
N64:Castlevania (64) - 3D Castlevania game mixing action and exploration elements from across the series along with elements of Resident Evil and Tomb Raider. ****
Castlevania: Legacy of Darkness - Expansion of Castlevania 64 with new characters (up to 4) and altered/new levels. ****
PS2:Lament of Innocence - Devil May Cry meets Castlevania. **
Curse of Darkness - Devil May Cry meets Castlevania with a few more nods to SotN and Pokemon. (also on XBox). *
Wii:Castlevania Judgment - Castlevania meets Power Stone (fighting game). *
Gameboy Advance:Circle of the Moon - A blending of SotN and the original Castlevania in terms of gameplay. In terms of a pure gameplay experience, it rivals SotN. ***
Harmony of Dissonance - A SotN-style game that has a confusing dark world/light world mechanic. **
Aria of Sorrow - A SotN-style game closest in tone/gameplay to SotN, though it mixes in Megaman's gameplay element of stealing the enemies' powers. ***
DS:Dawn of Sorrow - A SotN-style game that plays just like Aria of Sorrow, but with better graphics, a worse storyline, and some interesting unlockables. I recall the castle design being not as good, either. **
Portrait of Ruin - A game that tries to mix the multiple character-swapping of Dracula's Curse with SotN, and adds stand-alone (but ultimately repetitive) level designs. **
Order of Ecclesia - A mix of SotN and Simon's Quest. (

-skipped it)
PS3/XBOX360:Castlevania Lords of Shadow - Complete reboot of the series, mixing together elements of God of War, Uncharted, and Shadow of the Colossus. **
3DS: Castlevania: Lords of Shadow Mirror of Fate - A mix of Lords of Shadow with some SotN elements. (

-skipped it)