I'm aware of the Mario RPGs, but when you say 'every' Mario, that's referring to the classic platformer.
I would agree with Zelda, but maybe I just haven't played enough Castlevania games - I don't remember any of them being more than arcade side-scrollers (some 3D.) When I think 'action RPG' it brings to mind games like Secret of Mana or Crystalis...
Castlevania (well, 'classic' Castlevania anyway) games do play as side-scrolling platformers, but are heavily RPG orientated and stat based. You collect and wear equipment, you level up, your character has a set of stats (STR, DEX, CON, INT, etc, the usual) and each hit on an enemy depends entirely on your stats and equipment. So yeah, they're much more than just arcade side scrollers.
My personal favourite was Aria of Sorrow, but that's on the GBA, I don't know if your DS can play that. Apparently Order of Ecclesia was pretty good, but the difficulty was a bit unbalanced.
I recommend Pokemon HeartGold if you liked the original Gold. You can still battle Ash(Red) and you can even unlock the music from the original.
I kinda got worn out after the latest pokemon on the GBA (Ruby/Sapphire, if I recall), but if I have any spare cash and I come across it cheap, I would consider getting it.
I've you've got access to a PS1/2/3, Xbox 360 or PSP then you need to check out Symphony of the Night, almost every CV game since then has borrowed from it in some way, it basically set the standard and now they struggle a bit trying to match it.
I may have good news for you: you get to fight some genuinely high-leveled Pokemon(I just fought a level 75 Dragonite, for example), so the difficulty that made the old Gold good is back.
Chrono Trigger DS The World Ends With You Mario and Luigi: Bowser's Inside Story I'm not the biggest RPG guy, but I loved all three of those immensely. And although this isn't an RPG, might I also suggest picking up a little-known awesome game called Bangai-O Spirits?
