I still have my own red mystery dungeon for my game boy. Hell, I remember playing a demo inside the best buy where they have the game attached to the wall and you try the game out. Just the idea of a mystery dungeon for Pokémon is either a step forward or a step back. The idea is original, and it was a fun new turn rather than beating the rival who's grandfather can't even remember names.
The graphics? They are above average for a game boy. Whenever a character speaks, you get a window of the Pokémon, and some facial expression if they are a common character in the story. You can distinguish the difference between Pokémon if you saw it on the screen so that's a start. The colors are all decent, and you do get an appealing video game.
The sound and music are all great. Some of the themes of maps in the game are catchy and the sound effects are appropriate. Even the sounds of used moves are fitting.
Mystery in my opinion is VERY addicting as the story progresses. I myself find it more fun to play than a regular Pokémon RPG. Every time you enter a map, it is always different. Different items, different enemy Pokémon, different layout.
The story? It is pretty similar with every mystery dungeon. A human turns into a Pokémon (hey I don't understand it either, and it was horribly explained in the DS mystery dungeon), they find a partner to go on their first adventure, they form a rescue team and save the world from legendary Pokémon. There is a major plot difference between the DS and GBA games, but both require only 2 little Pokémon to save the world.
There really isn't much to do besides walk around a map and go on adventures. The thing though is that the fun does happen in a map, but nothing between the adventures.
While exciting and fun, this is a very difficult game to beat. Not only do you have to worry about being defeated by a wild enemy, but there is also the matter of hunger. To make the game more realistic on an adventure, the character must also stay somewhat full, or their hunger diminishes their health. Also while you do regain health with every few steps taken, there are many, many wild Pokémon you may face and the amount of HP you have is similar to the way original Pokémon games work. About 2 or 3 more points with each level, start with a few dozen HP in the beginning. So there could be a dozen wild Pokémon lined up behind you, and the only sure way to lose them is to kill them all. So you will need a few restoration items.
The new concept for Pokémon called "mystery dungeon" is a huge dimension that was created and equally fun. It is full of, well, mystery, danger, and excitement. I do recommend this to you as the next game you are interested in playing.