I've enjoyed the Fire Emblem series on the GBA immensely. I've played
Fire Emblem to completion (working my way through an alt story line still) and I'm still working on
Sacred Stones.
From a game mechanic standpoint, the game is relatively easy to get into. There's a simple rock-paper-scissors system in place for both melee and magical attacks. For example, Axes are strong against Lances, Lances strong against Swords, Swords strong against Axes. There are also special weapons that reverse this orientation, or have other special properties (good against armored foes, good against cavalry, etc.) but everything is clearly marked out in the name of the weapon (ex. a lance named Axereaver) or quickly accessible using in game help. The quality of the weapons is also indicated by the descriptor of the weapon: Slim Sword, Iron Sword, Steel Sword, Silver Sword, etc.
The game is very clear, I think, about what items do what in the game, so you don't have to sift through the attributes of each one in order to figure out which is the best to equip. Also, there's no armor/gear system either, which in my books is a bonus. (I'd rather be planning strategy than managing my team's gear)
What I love most about the games are the stories and the characters. The main plot line in both games is really good and well scripted. You really end up coming away caring about what happens to the characters (especially because if you lose one, they're gone forever unless you restart the mission from the beginning). There's a relationship system in the game as well that fleshes out the characters too, and can change the endings in the game depending on how far you progress with those relationships.
There's a Fire Emblem DS game in development but no release date announced. FE also has games on the Gamecube and Wii, but I found that I enjoyed FE best in short to long bursts on a portable system while commuting on the subway or riding a train home. Sitting on the couch and playing it didn't feel the same.
---
I also really love the Advanced Wars series. I've played Advanced Wars 2 on the GBA (again, currently working playing it through the second time on a new difficulty setting) and I'm working my way through the new Advanced Wars: Days of Ruin. (Apparently AW

ual Strike is one of the best games to have on the DS)
Advanced Wars is more of a pure strategy game than an RPG - in the new game, units can level up 3 times, but that doesn't carry over from mission to mission. However again, the stories and characters in both games are awesome and the strategy gaming is quality.
Another simple system at work here, rock-paper-scissors, but lots of little details that give units certain specific roles to play.
Both games were designed by Intelligent Systems, incidental.