Metroid Zero Mission & Metroid Fusion on GBA are really good.

Super Metroid is a great game, though you may have to resort to a walkthrough due to it not giving you directions like in the Prime games. All of the Prime games (save for Prime 2, imo) are excellent and are really addicting. The other Metroid games for GBA are also great, though I prefer the Prime games. The original Metroid is horrible and not worth your money.

I've only played the first 2 Mega Man games, and the only one I recommend would be MM2.

As for Fire Emblem, I usually play for its addicting gameplay and great story. The ones for GBA are excellent, especially the Sacred Stones. The DS one, on the otherhand, is a total dissapointment, due to its horrible storytelling, though the gameplay is still somewhat intact.

I recommend getting Super Metroid and the first Metroid Prime, as they are the best Metroid games imo, and also Fire Emblem Sacred Stones if you can find it used at a game shop. You can buy Mega Man 2 off the VC for 500 points, which is a great deal for a great game.

I can't say anything for the Mother (Earthbound) games and F-Zero games, since I've never played them.

I'll get SM and MM when I have the time.
I just looked at some Fire Emblem gameplay, and I'll pass (it was Radiant Dawn). Turn-based battling is a bit annoying IMO.
I'll pick up F-Zero GX if I can find a copy at Gamestop.

This is my absolute final decision.