Gunstar Heroes (Genesis, 1994)

Treasure were one of the premiere game developers for the Sega Genesis.  Their games are characterized by having some of the most impressive and stylish visuals on the Genesis, which give even the technologically superior Super Nintendo a run for its money.  Their first Genesis title was the quirky and fun platformer Dynamite Headdy.  They also made the Japan-only run-and-gun game Alien Soldier, which features some of the Genesis's most impressive visuals.  Fans generally agree though, that their best game was 1994's Gunstar Heroes, a platforming shoot-em-up, and one of the best games on the Genesis.
In this game, you play as Red (and a friend may play as Blue in simultaneous multiplayer), who must recover stolen jewels that were taken from them by the traitor Green.  An evil General wishes to use the jewels as a means to awaken and control a doomsday device.  A la Mega Man, you may choose which levels you want to play in any order (up to a point).  No two of these levels are the same.  In a genre that mainly only focuses on combat in progressively more difficult environments, Gunstar Heroes uses this combat in completely creative ways.
The first thing that is creative in this game is the combat itself, and the weapon system.  There are four weapon types, and you may combine any two of them to make more powerful weapons.  For instance, combine flamethrower and machine gun and you get exploding bullets.  Combine laser and homing weapon and you get a homing laser.  I usually combine two homing weapons, which creates a kamikaze of rapid-fire homing projectiles.  Add in a broad range of melee attacks and you have a fairly diverse arsenal.
Each level is also crafted to be wholly original.  One level has you rocketing down a mine shaft on a robotic mining cart.  Another level has you piloting a ship through space, shooting at obstacles and dodging lasers.  My favorite level has you playing a board game where you throw a dice, move spaces, and then must complete an obstacle course or defeat a boss.  Another great thing about this game is its creative and challenging boss fights.  There is a large emphasis in this game on fighting bosses, and they are no exception to this game's streak of originality.
No, there aren't any messages or themes to explore in this game.  Yes, it is a game that highly relies on combat as a means for progression rather than creative problem solving.  However, there is an immense joy to be found in this game.  I think that games on the Sega Genesis were most at home in the realm of simple, arcade-style action.  Some of the best games on the system are this way.  Vectorman, Sonic the Hedgehog 3, and certainly Gunstar Heroes, are games that sought to push their platform's technical limitations to the very limits, and deliver a product that impresses and entertains, still to this day.