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.