This is maybe different from what you’re seeking, but SPL-T is a very engaging puzzler that can lead to flow states where you’re slicing your way through perfectly balanced stacks of blocks, watching their countdowns halve each time. It’s turn-based and iOS only. Fully deterministic, very simple, but my preferred strategy is still evolving every time I play.
Quite a few puzzle games came out in the late 80's and early 90's, probably hoping to be the next Tetris, but most of them are pretty forgettable. Nothing else ever really captured that same feeling, and certainly not its broad appeal. It's just so elegantly simple.
I think the ones that have stood the test of time the best are:
Puyo Puyo:
Somewhat similar to the versus mode of Dr. Mario, but a lot faster and with a much higher skill cap. Simple mechanics, but very deep gameplay. Sadly never got a huge following outside of Asia.
Magical Drop III:
Moreso than any other game, this one makes me feel like I'm a machine performing a sorting algorithm. I mean that in the best possible way. Money Puzzle Exchanger is a very similar game that requires more advanced planning.
Puzzle Bobble:
I never got into this series but it frequently shows up on these kinds of recommendation lists.
Tetris Attack:
The name is misleading, it has nothing to do with Tetris and plays nothing like it, but a great puzzle game nonetheless.
Devil Dice is a personal favorite, but never reached the popularity of any of the above.
Some other honorable mentions that I don't know enough to comment on:
Meteos
Landmaker
Cleopatra Fortune
Klax
Columns
The list could go on and on though.