which kind of wood could be good for this kind of work
If you have the choice you want a close-grained, hard wood for this sort of thing. Normally that will mean a hardwood, although yew (a softwood) would also fit the bill.
There are many decent possibilities depending on where you're located. Going over my memory of commercial puzzles I've seen in the past, numerous Asian-made ones I think used sheesham. More recently I think I've seen some made from rubber wood, which is neither as hard nor as close-grained but adequate nonetheless.
If you're in North America maple would probably be ideal, being easy to come by there and not particularly pricey. Some maples are softer than others, hard maple (sugar maple, rock maple) will be tougher as the name suggests, and although this makes it harder to work it may be worth it in the end product.
Beech would also be excellent if you can find it and birch might work as well. Although it's classed as open-grained I have seen 'executive' puzzles made from black walnut which indicate it can be suitable, and walnut is prized for it workability by woodworkers (being only a little harder than cherry).
which finish guarantees a good user experience (e.g. pieces slide smoothly).
I think you could get away with many things on something like this, including leaving the wood bare. I'm sure I've handled puzzles in the past which were bare wood.
Commercially I think most puzzles probably have a spray finish applied, which could be either varnish or lacquer. And with modern finishing moving away from high-VOC products it's likely that some are now finished with a waterbased finish or some kind.
My personal choice here would probably be a light coating of shellac, two or three thin coats brushed on. This would not be enough to build up much of a film on the surface but will partially seal it, enough that it won't easily get grubby from handling and slightly reduce any tendency for the pieces to expand/contract or warp with changes in humidity.
You haven't asked about shaping the pieces, but if high accuracy is important to the functioning of the completed puzzle then I'd give serious thought to cutting the internal notches by hand as though they were mortises. Or alternatively buying a suitable mortising bit for a drill and using it to do the same job.
If you do use a scroll saw you're surely going to need to smooth the sawn faces. For that I would highly recommend filing over sanding. If you don't have any files then glue abrasive paper to strips of hard wood so that it can be used in a similar manner to a file.
For sanding the external surfaces bring the wood to the paper and not the paper to the wood. Small pieces are nearly always best sanded this way, with the paper flat on the table (taped down taut or glued in place on a scrap board) and the pieces rubbed over it, rather than attempting to hold the workpiece in one hand and a sanding block in the other and rubbing them together!
You only need to sand up to between 180 and 220 grit.