[metabagel]

Can't go wrong with Portal, although I had to look up a walkthrough from time to time in order to get past a puzzle, especially the end puzzle. I think it should play pretty well for you on Ubuntu and be a lot of fun.

Portal 2 is even better than the first one, but play them both.

[renjimen]

Seconded. And play Half Life 1 and 2. They’re arguably the best single player FPS games of all time.

[bhattisatish]

I watched couple of Half life videos/movies and I found the story line engaging. I haven't tried playing the games though. I guess next step will be that, in case they support controllers as I don't use mouse.