For replayability, I always come back to these games:
DS
Castlevania: Dawn of Sorrow
This is an action/RPG style game. I love replaying this game even though I have done it many times, I like the strategies for defeating bosses and using souls in a creative manner or attempting to go through the game using bad equipment (I once defeated the final boss on level 2 using the beginner's weapon. This is not possible unless one knows how
). Even if you don't replay the game as many times as I do, once you've beaten the game, you're rewarded with a new game+ with extra options and an entirely new game mode which is just as fun as the original game.
For some reason, I did not especially like any of the later DS Castlevania games. Too linear perhaps.
Ouendan 1 & 2
These are rhythm games. I couldn't say which one is better, the second one has a lot more songs and nicer art but I personally prefer the songs on the first one. I play them both equally probably. They are Japanese, but you don't need any Japanese knowledge to play the game. If you have friends with DS', you can play with them even if they don't own the game. The game is entirely stylus oriented, I always like stylus-oriented games, but I know some do not.
Advance Wars: Dual Strike
This is a strategy game. Compared to the newer Dark Conflict game, this game is incredibly unbalanced but I think the art style and fun characters make up for it (I don't like the Dark Conflict art at all, but it is a good game if you care more about balance), the game has many, many modes to play in and once you've completed the game, you can play in all of these modes with all of the characters providing a unique game every time. The main campaign has different difficulty settings and each map has a completely different strategy for each difficulty setting, and the campaign is rather long! If you get bored of the provided maps or if you just feel like it, you can create your own map using the map maker, which is a fun tool in itself. You can play multiplayer with this game even if your friend does not have a DS, it is nice for those very lazy days, passing the DS back and forth.
Tetris DS
This is Tetris for the DS. It has multiplayer which can be very frustrating or very fun depending on one's opponent.
GBA
Game & Watch Gallery Advance
This has many old Game and Watch games and improved versions of them. They vary in style a lot, but the objective is always to get a lot of points. I wish they would make a new one!
There are loads and loads of excellent games for both these consoles, even better than the ones I have listed (maybe!), but these are the games I always come back to.
I felt so immensely geeky typing all of this out.