Since I only buy Linux-native games now, I'm always on the lookout for new companies and games to try.
If you're interested in more story-based adventure games, I can highly recommend WinterWolf /Tycoon Games. Nearly all of their games except one are available for Linux, and should run on nearly anything thanks to the usage of RenPy, the Python-based visual novel development tool.
Having played several games that used it, it's a very nice toolkit- it provides a nice interface, autosave & regular saves, dialog skipping, and other expected features.
If you've never played a visual novel game, it's like playing a fully illustrated Choose Your Own Adventure book- you're encouraged to replay it, either because you lost, or to see the rest of the game you missed because of your choices.
To see some fine examples of games that use this toolkit without fitting into that general mold, check out Digital: A Love Story, and Hearts of Fire, both by the same lady- Christine Love.