A cursory look at the English Wikipedia says it was PaRappa the Rapper (1996), but I find it hard to believe that no-one thought to turn performing music into a game during the 16-bit era. The SNES should have been powerful enough for something like リズム天国 (Rhythm Heaven GBA), for example.
I have an answer, but I'm not very confident in it.
If you do the smallest amount of due diligence and read the contents of the Wikipedia article, well first of all it lists Simon (the 1978 electronic toy), which is wrong for multiple reasons. That toy was inspired by an arcade game from 1974, and also, just because "call and response" is a musical concept doesn't mean that a game based on it is necessarily a rhythm game IMO†.
But the next paragraph starts with エアロビスタジオ (Dance Aerobics) for the Famicom/NES, which was released in Japan in February 1987! It used the "Family Trainer" (a.k.a. "Power Pad"), a weird peripheral that I guess later inspired DDR's dance pads. Looking at some longplay footage, it seems like the main gamemode involved stepping on the pad to mirror the instructor's movement, which happens to be synced to music. Wikipedia says repeated mistakes result in a loss, so I'm calling this a rhythm game. It might not have been popular, or any good, but it predates PaRappa by almost a decade.
Still, Wikipedia doesn't have a list of every game ever made, nor should it, and I feel like there were enough years between Strachey's Draughts and the Famicom for an experimental game to be made and then slip into obscurity, maybe on one of the home computers.
† So then what do I think constitutes a "rhythm game"? I'd say 1) it must have a goal (it's a "game" not a "toy"), 2) gameplay must revolve around a musical performance, and crucially 3) the player must be rewarded for doing their inputs in time with the beat i.e. with good rhythm (this disqualifies Simon).
Sega released an arcade game in 1976, "Rock n Bark", a variation on the previous year's "Bullet Mark", a light gun shooter that tasks the player with shooting targets in rhythm to a rock song played via 8track. I believe this fits your criteria of being a game and involving a music performance, but unfortunately there isn't much documentation on the cabinet itself let alone gameplay details like if more points were awarded if you were "on the beat".
There is also a rhythmic EM game machine referenced in a Kasco interview referencing a commercial series that initially aired in 1969, but there is little to no documented information I've been able to find on that one.