Uo Poko?
Thanks, but that's not it.
Bah! I might even have the details wrong, it's weird how your memory can distort stuff sometimes. I think I would know it if I saw a screenshot of it, so if no one comes up with it, I had a brainstorm: Use RomLister to copy all the puzzle game snaps to another folder and then just browse through them. A lot faster than loading up every puzzle game rom.
And thanks for the game suggestions guys, got a chance to try a few of them, and this is the kind of stuff I'm looking for.

Stuff that's not just another Tetris or Puzzle Bobble clone (as great as those games are, I really don't need to have umpteen variants of them).