Bradtemple87 wrote:You could start with Street Fighter on almost any platform, but I say to pick a game that interests you. Don't think about character tier lists and what games people push on you. I believe any character can be played effectively and you can actually play better with a character you like versus picking someone top tier for advantages. Since you have an xbox 360, Super Street Fighter 4 is cheap and there is always someone to play against online if that interests you. The 2012 update is around the corner with character changes for the entire cast.
This is great advice, I'd also add that finding a game or set of games that your friends will also enjoy is key. The single player options in these games can vary from mundane to awesome, but nothing beats versus play with another human.
Dreamcast is an awesome place to start, every game Flake mentioned is fantastic. PS2 is another excellent place to find fighting games, but honestly every system you've mentioned has good ones. I'll try to throw out some that I've played and enjoyed for your systems.
Sega Genesis:-Yu Yu Hakusho: Makyo Toitsusen (one of the best, supports 4 players)
-Street Fighter II: Special Champion Edition
-Power Rangers
-Dragon: The Bruce Lee Story (kind of interesting 2P co-op mode and a fun 3P versus except for the fact that everyone has to be Bruce Lee LOL)
Super Nintendo:-Teenage Mutant Ninja Turtles: Tournament Fighters (AWESOME game)
-Power Rangers: The Fighting Game
-Gundam Wing: Endless Duel (this is actually like a sequel to Power Rangers: TFG, similar engine and same company, so go with this if you can)
-Sailor Moon S
-Killer Instinct
-Dragonball Z: Super Butoden 2
-Dragonball Z: Hyper Dimension
-If you get a Super Gameboy, you can enjoy 2 player versus mode on fighters like Samurai Shodown, Power Quest, Super Chinese Fighter GB, King of Fighters 95, and others with just one copy of the game.
Playstation 2:-King of Fighters 2002: Unlimited Match
-King of Fighters 2006 (or Maximum Impact 2)
-Hokuto no Ken
-Vampire: Darkstalkers Collection
-Street Fighter Alpha Anthology
-Street Fighter EX 3
Playstation 1:-Street Fighter EX series
-Tobal 2
Gamecube-Bloody Roar: Primal Fury
-Soul Calibur II
-If you have a Gameboy Player AND another GBA AND a link-up cable AND two copies of DBZ: Supersonic Warriors, then that game is pretty cool.
-Def Jam: Fight for NY is more of a brawler/wrestling game, but has quite a few fighting game elements to it, might be worth trying if you want another 4P game (and in the same vein, Ultimate Muscle: Legends vs. New Generation provides similar fun).
Xbox 360:-King of Fighters 13
-Guardian Heroes (12 player versus, you can't beat that!)
-WWE All Stars (obviously a wrestling game before anything else, but this one has a lot of fighting game elements going for it too and is really fast paced)
Dreamcast:-Psychic Force 2012
-Mortal Kombat Gold
-Do the Power Stone games count?

-Marvel vs. Capcom 1 is also pretty great in its own way
I'm sure I've left plenty of my favorites out, might have to chime in again if they don't get mentioned. There's A LOT to choose from, play as many as you can until you find one (or many) that you and your friends can enjoy!