Indigo Prophecy was definitely a fun experience, but it has more quick time events than actual puzzles. Still worth a look if you are looking for a good story (although it got rushed in the end so the finale isn’t great)
I’ll always have a soft spot for the old Sierra games because they were the first adventure games I played, but I think I’d recommend the old LucasArts games to new players nowadays. The LucasArts games were just better designed - they don’t have fail states and you can’t unexpectedly die so you are more free to explore.
My recommendation would be to check out “Day of the Tentacle”. In my opinion it is the best example of point and click games. I don’t know about Linux compatibility but it recently had a re release so I think it should work.