I know Cave Story has a Linux version.

CONQUEST!

Puddle, Bastion, Braid :)

I know it's very, very old, but NetHack is still a fabulous game with a ridiculous amount of depth. There's even a good chance it's already installed by default by your distribution.

Install desura and look up some games? It has lots of indie games on there, pretty sure you'll find a lot of games that you'll be able to run.

Deus Ex?

What's wrong with Linux Mint? Just customize it and install whatever desktop environment you want. Also, Revenge of the Titans and Closure can be added to the list.

I'm currently playing The Book of unwritten tales on Linux, and I recommend it, it's a fun adventure game :)
You should also try Rochard, it has a native linux version.

blobby volley

i think it has singleplayer, not sure. it's fun in multiplayer.

Super Meat Boy (but not on steam yet),
And Yet It moves,
Trine 1 & 2, (1 not on steam yet)
Kerbal Space Program,
Machinarium (not on steam yet),
Bastion,
Braid,

And a lot more.

I enjoyed a lot Braid, Dungeons of Dredmor, LIMBO and Trine 1 & 2 (the first is not yet on Steam for Linux), maybe give them another chance. I would recommend you Super Meat Boy and Bastion. The second one is a masterpiece, I hope you will like it.

By the way, there are a lot of titles which are remarkable, like The Journey Down (point-and-click adventure), Rochard (I haven't finished it yet) and Waking Mars (same here, but maybe it's not good as the previous titles). Let me know if my suggestions have been useful :)

Edit: I have forgotten to mention SPAZ, that is one of my favourite games in its genre.

Dwarf Fortress.

ULTRATRON

This is multiplayer but Counter Strike: Source

battle for wesnoth. Freeware, but good!

Titans Attack, Shank 2

Some old loki games, if you can get your hands on them (like alpha centaury). Though they are really hard to find. I also second westnoth. One more suggestion is warzone 2100