Order of Ecclesia is the one DS Castlevania I haven't played (Largely because I was burned out on Castlevanias designed in the spirit of Metroid). I've heard it's challenging and repetitive in design, yet has a lot of charm and good ideas mixed in. Dawn of Sorrow is more solidly designed from top to bottom than Portrait of Ruin, but Portrait of Ruin has more interesting game mechanics and eccentricities mixed into it. The Gameboy Advance-era Castlevanias play on DS Lite, as well. Aria of Sorrow is basically a better designed, but less graphically powerful version of its sequel, Dawn of Sorrow. Circle of the Moon is sort of a mash-up of Symphony of the Night and pre-SotN titles. Harmony of Dissonance is like Circle of the Moon, but leans more heavily toward Symphony of the Night in sensibilities, and is thus a lot easier. Castlevania 1 NES CLASSIC is also available for GBA. It's the starting point of Castlevania, and is solid in design and pretty challenging, although rather "plain" compared to later Castlevanias. (But you said you already played it)
If you have any way to check out Super Castlevania IV, via Wii Virtual Console for example, I 100% recommend it. Outside of Symphony of the Night, it's one of the highest ranked Castlevania games, and for good reason. Moody visuals and amazing action abound. The NES' Castlevania III: Dracula's Curse is another top 5 (or higher) Castlevania title. It can be pretty hard, but it's a great game, and it introduced Alucard in the series as an alternate helper character. Honestly, there are a lot of pre-SotN games worth playing. A lot of people would recommend Rondo of Blood--a middle ground between the earlier titles and SotN--but I'd say Dracula X (SNES), Bloodlines (Genesis), and Belmont's Revenge (Original Gameboy) are very high up there if and when they become widely available again. (That said, Rondo of Blood is easier to play and find). If you like more "questing," Castlevania II: Simon's Quest for NES has some of the most obscure puzzles in the series, and in some ways was an early spiritual predecessor to SotN. The N64 games, Castlevania (64) and Castlevania: Legacy of Darkness (Enhanced remix/prequel to the first N64 game) are really interesting mixtures of classic and later Castlevania titles in 3D. They're rough around the edges, and get mixed reputations because of it, but are very ambitious and atmospheric titles worth looking at. For my money, they're easily the best 3D titles in the series.
Keep an open mind with Castlevania. It has many different styles, and each player/fan has their own favorite mixtures of gameplay styles.
Last I checked, here's how to find the most available Castlevania titles on modern systems these days (via official download):
-Castlevania 1-4 & The Adventure ReBirth* (Wii Virtual Console) *The Adventure Rebirth is a Wiiware exclusive that almost completely re-imagines the Original Gameboy game, The Adventure.
-Rondo of Blood (PSP or PSP Vita*, Wii Virtual Console) *PSP/Vita Version includes a new 2.5D remix & a port of SotN, but I've heard the visual fidelity of the original Rondo isn't as good as it is on Wii.
-Symphony of the Night (PSP, PS3, XBox360).
-The Adventure* (Nintendo 3DS eShop) *A simple, charming, yet extremely difficult game in the series, partially do to intentionally sluggish controls.
-Harmony of Despair* (PS3 and XBOX360) *This is an HD multi-player game