How to download Games
A good choice is playdeb repo with a lot of games for ubuntu. You can go to website of playdeb find the game that you want and go to home page and download it.
PlayDeb
Games such as Max Payn or NFS are licensed by their owners and because they didn't created an ubuntu version you can't download any .deb after a legal purchase.
I however can suggest World of Goo. It costs only 20 bucks and it comes in a .deb package. See http://2dboy.com/games.php.
Furthermore I suggest you to check the following site because it is all about ubuntu games. Be sure to check todays game of the week. It's a free game and I believe downloadable as a .deb. http://www.ubuntugamer.com
Good luck, Martijn.
Urban Terror
It is self contained, and would not require additional packages to be downloaded. It has binaries for all major OS in the same package. Keep note this is a multiplayer game.
Link - http://www.urbanterror.info/news/home/
Wolfenstein: Enemy Territory
http://www.playdeb.net/software/Enemy%20Territory