Preferably on PC, you know, but I also have a PS4, a 3DS, and a rarely used Vita.

My problem with most rhythm games, especially the ones I find on PC, is the lackluster soundtracks. Most of it sounds like generic techno/dubstep cribbed from someone's Soundcloud. These games live and die on their soundtracks. It doesn't need to license Lynyrd Skynyrd and Bruno Mars or anything, but it'd help if it had a more Pop/Rock soundtrack.

For reference, some of the Rhythm Games I've liked in the past was Guitar Hero, Just Dance (but I don't have space for it anymore), Elite Beat Agents/Osu Tatakae Ouendan, Theatrhythm Final Fantasy and Persona 4 Dancing All Night.

I haven't played it, but have you looked at Crypt of the NecroDancer?

Zeo's non-GOG giveaway has had a number of other rhythm-based games over the past two years, but the only one still there I think is https://store.steampowered.com/app/231040/Beatbuddy_Tale_of_the_Guardians/ (also available here on GOG, but not in the GA to my knowledge)

Rhythm Heaven series is good, but might not be what you're looking for since it's more wario ware minigameish goofy personality stuff than actual songs, and it's also incredibly strict and has a fairly steep learning curve when you're first starting out.

though the 3ds title has a demo, and starts off a bit easier than the other titles with simplified versions of minigames.

Metronomicon is pretty fun and silly.

I really enjoyed these two:
Beatbuddy: Tale of the Guardians
Crypt of the NecroDancer
especially the latter. While it may still be a kind of a soundtrack you don't like I would say it's actually pretty neat. I had a blast playing it even though rhythm games and music like this are not usually my thing.

Here's Osu!

Stepmania.

And Frets on Fire.

Audiosurf lets you use whatever music you want. Because of that, it cant quite deliver as intense an experience as other rhythm games can, but you wont be complaining about the soundtrack.

Yup, another vote for Audiosurf, although unfortunately it is only available on Windows.
Another good one that lets you use your own music is Beat Hazard.

@Mr.Mumbles

That game looks cool.

@Darvond

I installed Osu yesterday. It feels weird to play that with a mouse, but I might get used to it. Stepmania looks interesting as well.

@bler144 @Ghorpm

I don't like Necrodancer, part of it is the soundtrack, part of it is the gameplay. It's more about keeping the same rhythm than having it ebb and flow with the music.

@MobiusArcher @babark

Audiosurf is alright, but its procedural nature does make it feel lacking that extra oomph you get from individually designed songs.

Not a fan of the genre myself, so I cannot recommend you any game in particular. But you may want to have a look at the Rhythm Café playlist of the LoadingReadyRun troupe.

If I'm way off here forgive me because it's not really rhythm based, but is very music based, how about Symphony.

I always loved how the pace of the music dictates the difficulty. The faster and harder the music, the faster and harder the baddies.

I played it with "One" the other day. The first five minutes were easy. The last two were brutal.

You haven't lived until you've bought Beat Hazard and turned Through the Fire and Flames into eight minutes of missile barrages and neon serpents.

I enjoyed Dedede's Drum Dash on the 3DS, which is an extension of the minigame from Kirby: Triple Deluxe.

Space channel 5 is in the dreamcast collection on steam. Also Beat Hazard is a decent game. Vib ribbon was goon on PS1 :D