The retro-arcade might not be the best place to learn these things (unless you have a knowledgeable guide with you). Not that you shouldn't go, but it's a hard place to learn anything.

It's easier to learn when you've got some more time and less pressure, so I really recommend buying a few, cheap, "gateway games" in various genres, that aren't too demanding on computer hardware. Lots of games are regularly under $5 at steampowered.com, humblebundle.com/store, or gog.com, and some have free demos. (But arcades, and "free to play" games, are mechanically set up to make you give them more money. It's easier to learn about the relationship between mechanics and genres without all that noise. That's why I'm recommending purchased games or games that are genuinely free.)

Do you have a PC or Mac? PC has a wider selection but lots of recent games are cross platform.

The following will give you a taste of a genre without overtaxing your computer, and these are frequently available very cheap. (Also, I tended towards lower-violence options when available, given your statement of preference earlier, and gave a bias towards "arty" games.) There are a lot of platformers here because it's a basic genre that you can find tutorials for; I also threw in a "walking simulator" because it's the easier kind of 3d game to make by far.

First-person puzzler: Portal

Puzzle: Sokobond

3d platformer: Psychonauts

Puzzle platformer: Braid or Fez

Precision platformer: Hmmm... VVVVVV? There's a free demo of that.

Metroidvania platformer: Aquaria

Roguelike platformer: Spelunky (still available in its original, free incarnation)

Roguelike: Crypt of the NecroDancer

RPG: Can't think of a good entry point here. Knights of the Old Republic, maybe?

Japanese-style RPG: Not a great selection on PC/Mac. Maybe track down Chrono Trigger by some means...

Action RPG: Torchlight

Japanese-style Action RPG: Recettear maybe?

Visual novel/Dating: Hatoful Boyfriend

Graphic adventure: Day of the Tentacle

Strategy: Hmm... Civizilation IV? The XCOM reboot? Any ideas?

Shoot-'em-up: Jamestown

Fighting game: Skullgirls (I thought Jamestown and Skullgirls did an admirable job of trying to train new players in genres that have become difficult to get into as a beginner)

Stealth: Hmm... Dishonored? Monaco?

Walking simulator: Proteus

Even cheaper option: Watch some "Let's Play"s or "Long Play"s on YouTube. Watching an insightful player play a game can be as illuminating, or more illuminating, than playing it.

Wha...? Those are all games from this millenia (save day of the tentacle)!

I say go with the originals! (Still gave you a +1 for compiling such an exhaustive list :))

Metroidvania: Clearly either Super Metroid (SNES) or one of the Castlevanias from the 8- or 16-bit era (though if you want to play the pinnacle of Metroidvania Game design, you need to pick Symphony of the Night (PS1)... its available on the virtual console on the PS3, AFAIK a version was released for the PSP, and there are rumours it might appear on Steam... its clearly worth the 20 bucks or so it still costs on virtual console!)

Fighting Game: Street Fighter 2, clearly. Not claiming it is the best, or most attractive battler.... but it was the one making the whole Genre popular back in the days. Also, the SNK Neo Geo Fighting games (King of Fighters, Fatal Fury, Samurai Showdown) are some of the finest 2D fighting games of all times.

Action RPG: Torchlight, really? Its a fine ARPG, but why not play the game that inspired it, Diablo?

Japanese RPG: well, good luck tracking down the classics on PC LEGALLY. If you have access to an emulator (and don't feel dirty handling downloaded ROMS), you will have access to them all though (though I don't think I need to warn you how illegal that would be... clearly buying the used cartridges and owning an old console is the better way)... some of the best though came out later on PS1, Don't know if you will be able to play them on PC, legal or not.

My all time favourite list:

- Breath of Fire IV (PS1) ... best JRPG Story ever. A Kickass Antagonist you can relate to. And actuall quite good graphics for its time

- Final Fantasy 6 (SNES)... one of the most epic JRPGs ever. Final Fantasy before it started to crumble under the weight of its own baroque story (which started with 7 IMO)

- Chrono Trigger (SNES)... a game with multiple endings, a story more clever than many current games have, and again kickass 2D graphics for its time.

JRPGs that are also worth playing

- Breath of Fire II / III (SNES, PS1)... the story is always kinda-recycled, and besides part IV these games are not the best of the best. Still very solid JRPGs with fun characters

- Final Fantasy 5 (SNES)... from a time when final fantasy games were still pretty hardcore. Had to level quite hard for beating the endboss. Not the best, but good.

- Chrono Cross (PS1)... story not on the same level as its predecessor. The graphics is extremly beautyful (for the PS1), locations sometimes breathtaking, and the music is one of a kind.

- Lufia 1 + 2 (SNES)... on of the lesser known JRPGs of the 16bit era, these games are actually quite good. Less advanced looking graphics than Chrono Trigger or FF6, and the AFAIK quite higher difficulty made these games be overshadowed by others at the time.

Jump'n'run: Do I even have to make recommendations here? All the Mario games, Sonic the hedgehow or Donkey Kong games...

Wha...? Those are all games from this millenia (save day of the tentacle)!

True, but that's why they're easily and legally available on one platform, and regularly go on sale all at the same time.

OP: for a legal way to access a lot of console classics (esp. Mario), go to your local videogame store and buy a used Nintendo Gameboy Advance, or the original Nintendo DS that still plays Gameboy Advance cartridges. A lot of NES and SNES games (and even games for other consoles) got ported or remade on the GBA.

True, but that's why they're easily and legally available on one platform, and regularly go on sale all at the same time.

OP: for a legal way to access a lot of console classics (esp. Mario), go to your local videogame store and buy a used Nintendo Gameboy Advance, or the original Nintendo DS that still plays Gameboy Advance cartridges. A lot of NES and SNES games (and even games for other consoles) got ported or remade on the GBA.

Also PSP / PS Vita seem to have gotten a lot of re-releases, at least of the PS1 classics. So if you still find it, you could grab one of those Vita TV consoles for cheap.

Then there are the emulation consoles. Most of them are not licensed, but given that they still need the original cartridges to play a game, and none of the original console makers really made a move against them yet (apart from sometimes selling their license for an OFFICIAL emulation console), they seem to be fine legally. Those old consoles are only sold used anymore, so the original producer does not make any money with hardware anymore anyway...

RetroN5 takes the crown as most awesome emulation console ever! Own it myself, love it dearly. Plays my old cartridges over HDMI, Upscaled to 720P with different AA options. Sound is also "supercharged" with bass boost and other options. Still owning an old SNES I can tell, games look and sound much better!

Add to that "automatic saving" (when you switch off the console, it will keep your game session, so you start at the point you switched off, even if you change cartridges between play sessions), and the fact that this console plays all SNES and Super Famicom, NES and Famicom, Mega Drive/Genesis, Gameboy and Gameboy Advance cartridges (Master System if you shell out for the Mega Drive adapter), ALL regional variants there are without skipping a beat, and the >100$ Price is easely justified!

The controllers are crap, but you can connect any original NES, SNES or Mega Drive Controller (or the US/JPN variants) instead. I suggest getting SNES/Super Famicom controllers, they can be had cheaply used online, and I think they rock (but then I grew up holding them for hours every day :))

Haven't found any game where there was any error (save avery slight graphics error with Secret of Mana, but could be down to the cartridge I bought used being crap)... still keep in mind the games are actually loaded to RAM and the hardware is emulated, which means purists will moan, but also that there CAN be games where emulation fails.

There is an official emulation console for the NEO GEO... not cheap at 200$, but given the price of the original hardware, and even worse the original software, and the fact that used consoles are hard to find and go for collector prices, not a bad price.

Especially given you get like 25 of the best known classics with the console for free, and some newer bundles chuck in twice or three times that.

The console itself is a "shell" for a portable device with its own screen and controls... but of course the fact that this "shell" looks like a NEO GEO console, and comes with a controller looking like the original one is more important.

I heard reviews that the portable devices screen and controls were crap, and while the shell and shell controller actually look like the real deal, they feel way lighter and cheaper (to be expected) and that the quality of the video output cannot match the original (the NEO GEO seemed to be one of the few consoles with GOOD analog video out).

Lately there have been emulation consoles put out for even older, pre-crash consoles. There was a big ruckus about the officially sanctioned ZX Spectrum emulation console, so if you want to play games from the Pacman era, that might be a good buy.

There are myriad of other emulation consoles. Of course, I would try to get one that uses the original cartridges and not one of the Android ones relying on downloaded ROMS. Not only because of legal issues, but also because the look and feel of a real Cartridge is priceless... and some of them are not even that expensive to buy used (some are collectors items and cost 200$+).

Be aware that while using old cartridges for things like Jump'n'runs and action games is mostly a cheap to midpriced options (cost from 10-40$ for good games, depending on demand and how rare the game is), the RPG titles tend to be way more expensive (start at 50$, but some of the best titles or more rare ones are hard to find under 120$).

Also be aware that you get different prices for getting only the cartridge, getting cartridge and booklet, or the full package. Given you only need the cartridge and the original booklets often were crap, you can save a ton by picking the offer just giving you the cartridge. Also, if you don't care about the condition of the cartridge, you can half the price again (games will be working fine, only the outer appearance might be... ugly).

The cheaper option for RPGs might be getting re-releases. Some are on Steam, but most get re-released on Android and iOS devices (seeing how modern phones offer many times the power of old consoles, that make sense). These are usually sold for around 20$ ... sounds like much, given that its a game with a full length of up to 80 hours, and costing 150$ used as a cartridge for the original system sometimes, that is not a bad deal actually (given those games quality of gameplay and story are WAY above what you usually expect on mobile).

Just be aware that most of those re-releases have reworked graphics and sounds. Which is awesome if you want to play a HD version, not so if you are a purist looking for the original expierience. At least what I have seen from the Squaresoft re-releases of Final Fantasy games from the SNES era made me want to play these HD re-releases even though I own the original games. Very nice reworks.

Oh, and never forget the PSP / Vita, some of the RPG have been re-released there AFAIK.

Then there are re-releases coming for PC / current gen consoles some of the blockbuster titles. FF7 is just getting reworked for Unreal Engine 4. Expect completly reworked graphics only resembling the original in parts... I would expect story and gameplay to not differ too much though.