"It's Mr Pants"!
Everyone misses that one, probably cause of the weird name but it's actually a clean, block-based tessellating game and it's absolutely brilliant
Probably double-ups below but consider these second-votes from a puzzle fanatic:
Kuruin Paradise (japanese sequel to kuru-kuru kururin)
Denki Blocks
Guru Logic Champ
Super Puzzle Fighter 2
Rampage Puzzle Attack
Sheep (all about herding sheep believe it or not)
Tringo
Zooo (aka Zoo Keeper in some countries)
Bust-a-Move
Puyo-Pop
Eggo Mania
Chu-Chu Rocket
Mr Driller 2
Tiny Toon Adventures - Wacky Stackers
Gem Smashers (similar to Game Gear "Columns")
Not sure if these count in your definition of puzzle but I'll list them anyway cause they come pretty close:
Turbo Turtle Adventure (ball rolling around mazes)
Super Monkey Ball (more ball rolling)
Bubble Bobble - old and new (arcade-puzzle)
Scrabble Blast (kinda like Boggle)
In homebrew:
Luminesweeper (port of lumines)
Blocktrap
and various Tetris-style things.