I'll be repeating some of what others said, but having grown up a Sega kid, I'd love to chime in (to emphasize).
Gunstar Heroes - DO NOT MISS THIS ONE!!
M.U.S.H.A./MUSHA Aleste - top-down shooter, incredible soundtrack, also DO NOT MISS!!
Thunder Force IV/Lightening Force - Side scrolling shooter, some of the best graphics on the Gen/MD, and great soundtrack.
Alien Soldier - really difficult to get into, but once you do, totally worth it. Platformer-meets-fighting game.
Gley Lancer - very anime-esque, but decent side scrolling shooter. Love this one for some reason.
Monster World 4 - there is an English mod for it, but otherwise it was a JAP only game. Very fun. Side scrolling action RPG
The Adventures of Batman and Robin - decent soundtrack, really advanced graphics for Gen/MD. Difficult.
Panorama Cotton - Kinda neat game, plays like Space Harrier. Hit or miss, either like it or don't.
Strider - Probably the most accurate port of the arcade game of its time.
Forgotten Worlds - Fun shooter, not true to arcades, but still fun.
Sonic 2 and Knuckles, Sonic 3 and Knuckles (combined carts) - Expands Sonic 2 to allow play with Knuckles, and Sonic 3 into a much, much bigger game with more secrets.
There's a lot I'm missing, but I think everyone else might have mentioned them already. If I think of more, I'll edit.
Edit:
Dynamite Headdy - Awesome platformer, has some neat gameplay aspects.
Rocket Knight Adventures - Another fun platformer, same character as Sparkster (RKA2), but I like this prequel more.
Aladdin - Not a huge fan, but the animation is superb and the controls are decent, you might like it more than I do.
Alisia Dragoon - Mentioned above, but saying it again because it's a great game. ;-)
Beyond Oasis - Great top-down action RPG. Lots of secrets. Mentioned many times, but again, reiterating.
Castlevania Bloodlines - Not a bad game. There are better Castlevanias, but this is the one we got.
Contra 4 - Another 'not bad' game. A lot like Gunstar Heroes in many respects, but not nearly as good.
El Viento - Decent action platformer. Not great, but fun at least once through.
Pulseman - Sega's take on a Megaman-like theme. Good game, nice style.
Final Zone - Really cool atmosphere, strangely awesome music. Decent game, but takes getting used to (mech-based, top-down shooter).
Granada - Not super great, but still fun for a couple tries. Top-down shooter where you drive a tank and blow stuff up.
Gaiares - Another great side scrolling shooter. Rather difficult compared to other shooters, has an interesting play mechanic.
Flink - There was a CD version that probably had better music, but never played it. Played this one instead. Platform game. NICE graphics!
Ghouls 'n' Ghosts - Pretty damn good conversion of the arcade game.
Golden Axe 1 & 2 - Mentioned before, but I'd avoid 3. It's terrible, and that's not just my opinion.
Herzog Zwei - A lot of people feel this is where RTS was born. It's like a mix between a top-down shooter and RTS. Your ship is your cursor. Play it, but you might want to read an online manual to see what the commands are first. Used to play one match against friends and cousins for hours (literally).
Puyo Puyo, Puyo Puyo 2 - Fun puzzle game, one of them is known as Dr. Robotnik's Mean Bean Machine in the US (and maybe Europe). Connect 4 or more of the same color in any arrangement to clear them.
RangerX - side scrolling action game, pretty interesting mech-based combat.
Red Zone - Amazing pseudo-3D helicopter shooter. Somewhat realistic in that your helicopter can run out of ALL ammo (not just missiles), needs fuel, and if your tail is hit, you start to spin. Fairly difficult game.
Space Harrier 2 - Fairly decent game much like the arcade prequel.
Star Control - Never played the PC version, but this was supposed to be a fairly good conversion of it. Bought this while waiting for Sonic to come out. :lol:
Subterrania - Kinda neat gravity-based side scrolling shooter. Very difficult at some points. Pretty fun once you get the hang of it.
Super Fantasy Zone - Pastel-colored side scrolling shooter. Rather famous series, fun game.
Syd of Valis/Valis SD/Valis Syd - Super-deformed version of the Valis series, really cute with bright colors. Decent platform game that I think is a little more fun than her life-sized counterparts, Valis and Valis 3.
Thunder Force 2, 3 - Take your pick. I like them all, they're all different, but 4 had the best graphics and music (imo, of course), while 2 had the most weapons. (HUNTAH. SIDE BRASTER. ROLL!!!!)
Tiny Toon Adventures - another decent platformer. Not as good as the SNES version, but still fun.
Vapor Trail - top-down shooter that's pretty enjoyable. Good in-game music, but it's used in EVERY STAGE, so it gets kind of annoying.
