Here's a selection of the genre selections from some of the leading game platforms:

Playstation is excluded because I couldn't find a browse by genre view for the web version of the PSN store
Playstation is excluded because I couldn't find a browse by genre view for the web version of the PSN store
All platforms have the following genres in common:
Action
Adventure
Indie
Racing
RPG / Roleplaying
Simulation
Sports
Strategy
Aside from "Indie" which arose fairly recently, these "classic" genres have been around as far as I can remember. Why did we wind up with these particular genres? How has their meaning changed over time? How far back do their origins go?
To answer this question definitively would be a major undertaking, so in this particular article I'm just going to travel briefly back in time to the late 80's and early 90's, looking only at Nintendo (specifically Nintendo of America). If this article proves interesting I might do some other eras and platforms (starting with SEGA).
Methodology
What I'll do here is go through old packaging and advertising material for the platform in question, looking for formal genre markers. These are explicit labels and/or emblems that are part of an official classification scheme by the platform holder itself, whether that's directly on the game package or in some kind of catalog listing.
As you'll see, in this early era, formal genre markers were actually fairly rare!
NES
Our first stop is the Nintendo Entertainment System, or NES. Poring over old box art and issues of Nintendo Power, I was only able to find formal genre markers in two places: "Players Guide" magazines (special bonus magazines included with a Nintendo Power subscription that showcased a variety of games from each of Nintendo's platforms), and the "Black Box" series of early NES titles.
Let's start with the NES Player's Guide, which conveniently starts with a genre classification "Color Guide":

These genres match the genre emblems found in the "Black Box" series of game packages. You can see "Action Series" prominently displayed on this copy of Super Mario Bros:

As far as I can tell, exactly 30 games were released under this packaging format. Future releases took on more illustrative packaging art, and dropped the explicit genre callouts:

Nevertheless, between the Player's guide and the Black Box series we have some decent information on how Nintendo of America was classifying their games in this period:
Genre | Notable Titles |
---|---|
Action | Balloon Fight, Clu Clu Land, Ice Climber, Kung Fu, Pinball, Super Mario. Bros, Urban Champion |
Adventure | Zelda (1 & 2), Metroid, Castlevania, Kid Icarus |
Arcade | Donkey Kong (1-3), Mario Bros., Popeye |
Sports | 10-Yard Fight, Baseball, Golf, Pro Wrestling, Slalom, Soccer, Tennis, Volleyball |
Education | Donkey Kong Jr. Math |
Light Gun | Duck Hunt, Gumshoe, Hogan's Alley, Wild Gunman |
Programmable | Excitebike, Mach Rider, Wrecking Crew |
Robot | Gyromite, Stack-up |
And here's the 90 titles in the Player's Guide:

Action, Adventure, Arcade, and Sports are familiar to modern eyes, and even Education isn't so far out – but genres like Light Gun, Programmable, and Robot are notably dated.
Light Gun games straightforwardly make use of the Nintendo Zapper.
Programmable games seem to feature some sort of customizability – such as Excite Bike's track editor
Robot games (both of them) are compatible with the R.O.B.
Nintendo is famously credited with resurrecting the home video game market after the notorious Atari Crash, and the package design and presentation of their first 30 games seems to tell a story of earnest transparency meant to win back trust – instead of fanciful illustrations that look nothing like the game as in the Atari era, you have simulated pixel art: what you see is what you get. The genre emblems and screenshots might have been an important part of their customer and dealer education – particular when highlighting unique and interesting features such as the Light Gun and the R.O.B.
As Nintendo found their footing and gained confidence, the overly literal box illustrations and genre callouts seem to have disappeared.
But let's return to the genres that have persisted to the modern day – Action, Adventure, Arcade, and Sports.
Arcade
This genre still lives with us today, but as actual arcade machines fade further into obscurity so does its contemporary meaning grow ever more muddled. But back in the NES era, this genre had a very clear and objective meaning: "This is a conversion/port of a coin-op game". This genre signified nothing about the gameplay style, mechanics, or tropes, merely that the original version was played on a literal Arcade cabinet.
Sports
Another very straightforward genre, which unlike Arcade