Neir Automata has an absolutely banging soundtrack. You need to "finish" the game I think 3 times to see the final ending. Push through the run as 9s it is worth it. The ending has all the feels and the ending song is with it is phenomenal.
To The Moon has a beautiful soundtrack and a story which made me cry. It's not a long game, I highly recommend it.
Syonara Wild Hearts is a video game music album. It's really simple mechanically but the songs are great and it's a proper Zen game.
Journey has a wonderful sound track, just get to like level 3 where your doing the big slide downhill and tell me that's not magical.
Similar to Journey (but not quite as good) is Gris.
Bastion has some excellent songs and is a short experience.
Terraria has a brilliant soundtrack and great gameplay, very little story though. Great in multiplayer so find a friend.
Death Stranding has some great songs, a bit to spread out though. The story is Kojimas usual eclectic madness but I enjoyed it.
The whole set of NES Mega-Man games had amazing soundtracks, although 2 is the best. There's barely a story there, but the gameplay is solid.
Final Fantasy VI has Dancing Mad, and that alone would be enough, but the whole damn thing is just amazing, especially the Opera.
Similarly, Final Fantasy VII had a stellar soundtrack, including the holy-shit-this-is-amazing One Winged Angel.
All Final Fantasy games have great soundtracks, but these two are my faves
Someone mentioned Terraria, and I would be remiss if I didn't second it. Not much story there, but I've been playing it for like 12 years and I'm still happy every time I start it up.
The Elder Scrolls games from Morrowind on all have bangin' soundtracks. Oblivion had the best one (although Morrowind and Skyrim are both better games, IMHO).
Tempest 2000 for the Atari Jaguar of all things had a phenomenal soundtrack. Seriously, it it was one of the first games in the US to have its soundtrack sold in stores. And it stands up.
I'll add more if I think of them. Most of the others I can think of have already been mentioned.
ETA:
Chrono Cross, I can't believe I forgot it! That OP is unforgettable, and yet somehow I managed to forget it! The game itself pales in comparison to its predecessor (Chrono Trigger, which also has a great soundtrack), but it's not bad.
On a similar note, the original Wild Arms had an excellent soundtrack with a western theme. Actually, the whole Wild Arms series has good music, but I just couldn't get past one of the main mechanics that showed up in 2 and stick around.
Another one I can't believe I forgot, Nights: into Dreams had the best soundtrack on the Sega Saturn. It's just perfect for the game, not a bad tune in there.
Somehow, nobody's mentioned Cyberpunk 2077 yet. Every track in this game goes so incredibly hard. The in-game radio stations are all full of absolute bangers, and even the ambient world music is fantastic and sets the mood for every scene. It's one of the few games whose soundtracks I listen to on its own.
I can also recommend FTL, Risk of Rain and Risk of Rain 2. Really good OSTs, I'm listening to all of them regularly. They've also got great gameplay! But they're rogue-likes so basically no story in case that bothers you.
Secondly anyone who said FURI - that game is a masterpiece and the OST is so well tied into the fights it's hard to separate them. Seriously, they gave the artists details on the bosses and their arena, fighting style and other notes and said make a song that fits
Hollow Knight (Great metroidvania, even better soundtrack),
Journey (It’s just good. I struggle to describe it any other way),
Project: Wingman (Neat game about blowing things up in planes. Has a fun, dramatic soundtrack.),
Cassette Beasts (An open world monster catching rpg like Pokémon. The soundtrack is good, although some people aren’t fans of the lyrics.),
Cloudpunk (A cyberpunk open-world exploration game. Really great ost to match the theme. Also, the game has exceptional story, especially the City of Ghosts expansion.)
I see some Final Fantasy mentions, but I'm throwing Final Fantasy Tactics in particular into the ring.
Great gameplay (min-max to your heart's content) that will let the player fail. Also will let the player soft lock themselves and require loading an earlier save if they didn't have "optimal" builds for some encounters...
It has a story! That moves forward all of the time! Just let it happen and don't think too much about it. You're a mere mortal fighting up against gods at some point. Maybe?
Great soundtrack! My personal favorites are below.
Caveats with hollow Knight story: you won't know a lot about the story until you watch mossbag videos after getting to one of the endings.
Hades (OST + gameplay + story)
Genshin (OST + gameplay + story)
Caveats with genshin gameplay: only the exploration and some quests are good. All other gameplay should be ignored (or doused with fire). The exploration is actually one of the best open world exploration I've played, and I've played Witcher 3, botw, AC: black flag, arkham series, and more.
Caveats with genshin story (context: currently on version 4.0+):
Side stories released on or after 2.0 are good.
Main stories released on or after 3.0 are good.
All other stories are generic af and Paimon is annoying.
Final Fantasy XIV has a diverse soundtrack and a terrific story, but it is a huge time commitment. The story starts off pretty slow and takes a long time to build up.
It very much depends on your taste in music, but Hellblade: Senua's Sacrifice OST is absolutely amazing, especially considering it's all original scores (I think). After beating the game I put the OST on repeat for several days
Undertale in case you haven't played it yet... you've played it, right?
zero escape. going in blind is a must. at least 999 had really banger music and nice puzzles and story. 999 also had its story made for the 3DS, so it's best if you play it on a DS emulator. it's also similar to danganronpa at least stylistically, and makoto has a zero escape logo on his hoodie
bloons td maybe. the music might not be that good but they're still bangers
Earthbound and Mother 3 could be exactly what you're looking for. There's just nothing quite like them OST, story, and gameplay wise.
Little Nightmares and Little Nightmares 2 also have excellent music that perfectly complement their soul-squeezing visuals and gameplay.
Portal 2 has very little music but it is GOOD, and perfectly timed to key moments in the story. Also top notch unique gameplay, obvs.
Skyrim music is iconic for a reason.
OFF's music is similarly iconic and its story and visuals so unique and engaging you'll likely forgive it for being unapologetically RPG-maker. The latest English translation (3.0) is considered the most faithful to the original French.
FRACT OSC is a "musical exploration game" where you directly influence the soundtrack by interacting with a beautiful, surreal puzzle landscape with Tron-like visuals.
This is all going to be "great gameplay" rather than "great story".
If you have a way to play 3DS games and a tolerance for punishment in your JRPG dungeon crawlers, the Etrian Odyssey series has some of Yuzo Koshiro's best work.
Finally ... Monster Hunter is an incredibly fun and addictive game series, and though it doesn't center the music quite as much as a typical JRPG does, it's got some great stuff. I particularly like the soundtrack of MH: World -- although the newer game MH: Rise tried something new with its mostly choral arrangements, I think they are not quite as memorable overall.
Arena battle from Monster Hunter: World (it's particularly impressive the way this theme, the small-monsters arena battle theme, and several of the town themes reuse the same melodies in different arrangements)
Admittedly the story is a bit thin… the game play is purposefully enraging… but it gets a big ol’double check mark on the OST requirement thanks to the Tokyo Ska Paradise Orchestra.
On a totally different note and tone, Last of Us. I dig anything Gustavo Santaolalla.
Guilty Gear not even getting mentioned once is criminal, the entire franchise has amazing music, to the point where the fanbase and the fighting game community likes to joke that they get a free game with every new music album whenever a new game comes out.
To add to this, basically everything Daisuke Ishiwatari makes, who is mainly responsible for almost everything about the game.
Lineage 2, I especially like the Dion theme. It's an old MMORPG though so when it comes to the question of a great story and/or gameplay... well I wouldn't recommend it lol. Even though I've spent a lot of hours in that game
Caves of Qud doesn't have a very big OST but I happened to absolutely love it. The game is similar to Rogue (or more directly Dwarf Fortress adventure mode), as in time only passes when you move and everything is represented by a tile, but it has pretty good controller support as of a recent update.
Undertale, love the Temmie Village song. The OST can be heard in all kinds of videos. Maybe since you liked ULTRAKILL (based on graphics), you'll like Undertale.
NieR:Automata is an absolute banger. It has a banger of a soundtrack and a really great story. I personally love the park area and the forest.
Subnautica, the OST, really helps to create an immersive experience. It is sometimes mysterious, it can be dark but also adventurous. The music kind of guides you through the uncharted lands.
The Legend of Zelda: BotW I know, it's a WIIU/Switch game, and I know TotK is out, but the design and the music of the game are fitting so well together. The OST is so incredible.
I don't see this mentioned enough, but persona 5 (specifically recommend persona 5 Royal) has a really great OST. As you play the game you unlock better versions of the same tracks, including vocals. It's actually really jazzy, and quite catchy! The wife and i will jam to the vocal tracks on road trips.
The game is also very good, with an interesting story! It's kinda weird in a fun way! It's like.. a pokemon-esque turn based jrpg with some like real world maintenance aspects (relationships, work a job, go to school), with great music
I absolutely loved Pokemon USUM‘s OST and was heartbroken when I found out the OST release was just like 1 minute long tracks that you couldn‘t easily loop (obviously it looped infinitely ingame)
Sonic games usually have great music but Sonic Mania in particular is full of bangers, highly recommend it.
Undertale's soundtrack has been memed to death but it's honestly really good.
If you're still in the mood for visual novels the Phoenix Wright Ace Attorney games have some incredible soundtracks too.
Also, for something slower, I must give a shout out to The Sims 1. It's suave as hell and very, very catchy.
Some games with soundtracks I particularly enjoyed over the last couple years:
A Hat in Time - a cute, fun collect-a-thon platformer with a kickass soundtrack. This one is particularly fun to play and hits nostalgia vibes for the early 3D Mario games.
Shantae and the Seven Sirens - 2D platformer with an energetic chiptune-y soundtrack. The game itself is OK, but the soundtrack is what really made this one for me.
Subnautica - underwater survival and crafting game with a soundtrack that set the mood very well
Demons Roots - 18+ RPGMaker game where you lead a demon uprising to reclaim the surface world, invading country after country freeing slaves as you go. Very dark game that is unusually good for the type of game it is. If you're not put off by the RPGMaker doujin wabi-sabi and are tolerant of adult content in games this one is worth a look. There are some absolute bangers in the soundtrack.
Pyre - Lord of the Rings meets 3v3 basketball with a very enjoyable soundtrack by Darren Korb (Bastion).