I hope readers don't mind that I spoiled one of Nikoli's sample puzzles.
One of the classics is Numberlink. In Numberlink, you're supposed to draw lines between each pair of identical numbers. There is always a unique solution, and this solution just so happens to use every square.* But even though there is a unique solution, you're not supposed to solve the puzzles by deduction. You have to use a lot of guessing and intuition, or it would be too difficult. MellowMelon has a guide on how to solve them.
*If you ever download a Numberlink app for a mobile device, they often require that every square must be used, rather than having a unique solution that just so happens to use every square. I consider this a serious travesty, and do not recommend Numberlink apps.
I would like to contrast this with a lot of puzzle apps out there which do not have unique solutions (eg see this review). Usually this isn't because they've been designed as non-deductive puzzles, but because the programmers couldn't be bothered to check for unique solutions. This is the worst.
This was a randomly generated puzzle from Tatham's puzzle collection.
Moving away from pencil-and-paper puzzles, there is a game called Blackbox. It can be played with two people, but it's really better to play against a computer. In Blackbox, there are some balls in a box, and you're supposed to figure out their positions by shooting some lasers into the box. You can't tell what the lasers do inside the box, but you can tell where they come out, if they come out. There's a lot of room for deduction here, though solutions aren't unique. But it's really more fun to try to figure it out based on the smallest number of laser beams. Since you decide where to shoot the lasers, it tastes a bit like experimental science.
You can play Blackbox within Simon Tatham's puzzle collection, which has free mobile app versions. I also recommend Eric Solomon's hexagonal variant.
Lastly, I'll mention a card game I just bought called Hanabi. Have you ever seen those logic puzzles where people wear colored hats, and can only see the colors that other people are wearing? Or perhaps the puzzle of the three foolish/wise men who wake up with marker on their faces? Hanabi is sort of like that, because each player holds their hand backwards, so that only the other players can see. Players cooperate by giving each other hints to play the right cards in the right order.
But while the colored hats puzzles are deductive, Hanabi is not because you can't be sure that everyone is playing perfectly (and no one knows what that would even look like). Furthermore, there's never quite enough information to play deductively! It's a lot of fun.
In conclusion, there is plenty of interesting puzzle-space to explore beyond deduction.