Wait for the SEGA Mega Drive Classics Collection to go on sale on Steam or any other DD site then buy it. I recommend the Shining Force games, they are SRPGs.

Shinning Force is the most obvious. It is available on GG, Genesis, and Saturn.

Also, Albert Odyseesy on the Saturn. Plus, Panzer Dragoon Saga -- if you can find/afford.

Mike from Morgantown

Well, since you say you want to get into "Sega" gaming, I'll focus on 1st party affairs:

Definitely the Phantasy Star series, specifically the first one (Master System) and part two (Genesis).

The Revenge of Shinobi is also a great game (try to find the un-edited version), as well as the Streets of Rage series (part two is my favorite), and the Shining series.

Other games I liked: Golden Axe, Space Harrier 2, Mystic Defender, Sword of Vermilion (Genesis), and Wonder Boy in Monster Land (Master System). And I'm sure you're familiar with the Sonic series.

If you have a Wii, you can get many of these games on the VC, along with the arcade perfect versions of Space Harrier, Shinobi, Golden Axe, and Altered Beast.

Every genesis game in my collection except Batman: Forever....  Also, make sure you try cliffhanger.  It's one of my favorites.

Sonic 3 & Knuckles is a must, and, so is Cliffhanger, Vectorman, QUACKSHOT, Streets of Rage 2, Road Rash 2, Battletech and BOOGERMAN!

EDIT: Remember to try Cliffhanger.

The 3DS versions are ports....... but you can adjust the screen size to full ect and theres other nifty features like no blur.

Game Gear/Master System.............. Pick up the Sonic's & Shinobi's, but as mentioned above, theres already Game Gear games available for the 3DS (and theres more on the way)

So the focus here is going to be Megadrive/Genesis and Saturn Games.

Megadrive/Genesis

You have a PS3 right........ well, theres more vintage collections on the way (they come in 3's) theres a Wonderboy triple pack, a Streets of Rage triple pack (with online co-op, thus making it appealing to buy the, over the Ultimate collection which does not offer online play) and the 3rd pack is a strange one, it's 3 different franchises alltogether (The Revenge of Shinobi, Super Hang-On and Alex Kidd in Miracle World)

Most of SEGA's best games are available on VC/XBLA/PSN, but i'll list some games and then i guess you could consider them for purchase on any console of your choosing (even a Megadrive if you want to be authentic)

List of SEGA Megadrive/Genesis games that are well worth a look..............

Streets of Rage 2
Streets of Rage 3
Golden Axe 1
Golden Axe 2
Shinobi III: The Return of The Ninja Master
The Revenge of Shinobi
Eternal Champions
Sonic & Knuckles
Sonic 3
Sonic 2
Sonic
Super Street Fighter II (Megadrives & Saturns have AWESOME d-pads, so fighters play excellent on them)
Castle of Illusion: Starring Mickey Mouse (awesome platformer)
Shadow Dancer: The Secret of Shinobi
Moonwalker
Road Rash
Road Rash 2
Micro Machines
Micro Machines 2: Turbo Tournament (up to 8 players due to the at the time unique cartridge)
Outrun
Ristar
Chakan
Kid Chameleon
Earthworm Jim
ToeJam & Earl
Dick Tracy
James Pond
The Punisher
Dragon: The Bruce Lee Story
Cool Spot
Art of Fighting
World of Illusion: Starring Mickey Mouse & Donald Duck
Ghouls 'n Ghosts
Alladin
Columns
Tazmania
Mortal Kombat 3
PGA Tour Golf II (sports, but an excellent game)

Theres obviously many more, perhaps wiki wil have an entire list or somthing.

SEGA Saturn games to look out for........

Fighters Megamix (why this is not on VC/XBLA/PSN yet is beyond me, one of the best one on one fighters of ALL TIME)
Radiant Silvergun
SEGA Rally Championship: 1995
Virtua Fighter 2
Fighting Vipers
Last Bronx
Nights
Decathlete aka Athlete Kings (sports again i know, but fun as hell in multiplayer)
Manx TT Superbike
If you invested in a lightgun you could also play House of the Dead & Virtua Cop 1 & 2
Virtual- On
Sega Touring Car Championship
Theres also a TONNE on SNK & Capcom crossover fighters available for the Saturn (the best d-pad in the WORLD) stuff like Xmen- Children of the Atom &Marvel Super Heroes, and theres King of Fighter '95 and Street Fighter Alpha ect
And the ACE in the pile....... Guardian Heroes

erm........ i have been typing for what seems like ages, that should cover it.

i know i missed out RPG's but they have never been my cup of tea.

Lastly............. NO HOME is complete without a SEGA Dreamcast and a copy of the almighty Shenmue...!!!!

This is just off the top of my head, so I'm sure I'm forgetting some of my favorites. There are just so many must play Sega games.

Master System

-RPG:
Phantasy Star
-Adventure/Platforming
Sonic 1,2&Chaos, Wonder Boy in Monster Land, Wonder Boy III, Alex Kid in Miracle World, Alix Kid in Shinobi World
-Action
Fantasy Zone

Genesis

-RPG
Phantasy Star II,III,IV, Beyond Oasis, Crusader of Centy
-Adventure/Platforming,
Sonic 1,2,3,Knuckles, Ristar, Dynamite Heady, Contra Hard Corps., Castlevania Bloodlines, Wonder Boy in Monster World, Shadow Dancer, Shinobi 3, Revenge of Shinobi
-Fighting
Street Fighter 2 Turbo, Eternal Champions, TMNT Hyperstone Hiest
-Action
Gunstar Heroes, Jurassic Park Rampage Edition, Subterranea, Red Zone, Zero Tolerance,
-Horror
Splatterhouse 2,3,
-Strategy Shinning Force 1,2, Herzog Zwei
-Racing
Virtual Racing

Sega CD

-RPG
Lunar, Lunar 2 Eternal Blue
-Adventure/Platforming
Snatcher, Knuckles Chaotics, Sonic CD, Monkey Island
-Fighting
Eternal Champions
-Action
Rebal Assault
-Strategy
Shinning Force CD

Saturn

-RPG
Panzer Dragoon Saga, Albert Odyssey
-Adventure/Platforming
Astral, Pandemonium, Croc, Tomb Raider, Nights Into Dreams
-Fighting
Virtua Fighter 2, Virtua Fighter MegaMix, Last Bronx, Dead or Alive, Fighting Vipers
-Action
Burning Ranger, Panzer Dragoon, Panzer Dragoon 2 Zwie, Virtua Cop 1&2, House of the Dead
-Horror
Resident Evil, Enemy Zero, Deep Fear
-Strategy
Shinning Force 3
-Racing
Daytona USA CCE, Sega Rally CE, Wipeout 1&XL

Dreamcast

-RPG
Grandia 2, Skies of Arcadia, Phantasy Star Online, Silver, Omikron The Nomad Soul, Record of Lodoss War
-Adventure/Platforming
Stupid Invaders, Elemental Gimmick Gear, Shenmue 1&2, Sonic Adventure 1&2, Shadow Man, Soul Reaver, Eccor the Dolphin
-Fighting
Virtua Fighter 3TB, DOA 2, Project Justice, Marvel Vs Capcom 2, PowerStone 1&2, Bleem: Tekken 3
-Action
Rez, Mobil Suit Gundam: Rise from the Ashes, Headhunter, House of the Dead 2, Bleem: MGS, Jet Grind Radio Sword of the Berzerk: Guts Rage, Alien Front Online
-Horror
Resident Evil Code: Veronica, RE2&3, Carrier, IllBleed, Dino Crisis, D, Alone in the Dark
-Racing/Driving
Crazy Taxi 1&2, Sega Rally 2, Daytona USA, Looney Toons Space Race, Tokyo Extreme Racer 1&2, Metropolis Street Racer, Sega GT

NiGHTs into Dreams and Panzer Dragoon 1/2 (and Saga...if you have the cash) all for the Sega Saturn. Great games, I have very fond memories of them.

If you want multiplatform games then also try Pandemonium, Resident Evil and Tomb Raider.

Oh man, as Ronster already said, another must-play Sega game on Genesis is Castle of Illusion: Starring Mickey Mouse. I can't believe I forgot that!

And regarding 3rd party Genesis games, in addition to the already mentioned Ghouls 'n Ghosts and Castlevania: Bloodlines, you absolutely cannot miss Thunder Force 3 and M.U.S.H.A., which are arguably the two greatest space shooters ever made.

CASTLEVANIA: BLOODLINES. Easily one of the better Genesis games I've played.

TMNT: HYPERSTONE HEIST. Again, one of the better Genesis games I've had the pleasure of playing. Similar to Turtles in Time.

STREETS OF RAGE games. All very fun games.

MICHAEL JACKSON'S MOONWALKER. While not a masterpiece, I recently played and enjoyed this game quite a bit. Recommended if you are a MJ fan and/or like quirky games.