Soleil (aka Crusaders of Centy) for Sega Genesis is one of my favorites!
Some consider it to be Segas answer of The Legend of Zelda: A Link to the Past.
To me it is much more interesting than that. It has cute and vibrant graphics, good music and finally a story with a message.
Not the ususal "save the princess, rescue the kingdom".