The quickest way to find small games is to go to a website hosting files from the “demo scene”. One very significant part of the “demo scene” is coming up with tiny little demos or fully playable game whose .exe fits in a given size, such as 4k, 32k, or 96k. 4k gives you a very basic Tetris clone; 32k can give you a remarkable playable game in the vein of a 1980s or early 1990s Amiga or Atari ST game. 96k can give you a small but complete full game; there’s even a playable First-person shooter that fits in 96k (but, alas, can be finished in about 15 minutes).
The website I used to find demos was http://www.pouet.net/; the page which starts to list the tiny playable demos is at this link.
The one I like the most is a 32 kilobyte PacMan-style game. This got a few bad reviews when it first came out, but ignore them; the game has since been updated with sound added to the main game and the collision bugs people complained about have been fixed.
Some other notable demo games include a Tempest clone with 21st century graphics and sound, complete with configuration menus in only 96k (but the extensive eye candy sometimes makes gameplay a little difficult, and the screen moves around while playing in a way that can give you a headache), a 32k clone of a late 1980s platform shooting game which while beautiful and groundbreaking for its time, has hard-to-use controls, and a 32k clone of a late 1980s platform jumping game that, while amazing, is a very challenging game and the controls are a little awkward.
Another place to find tiny games is http://www.acid-play.com/, a listing of thousands of Windows freeware games. Finding diminutive games is a little harder at this site; there is no way to sort games by size. However, each game has its download size listed, which makes it possible to browse for small games.
There are a few tiny gems here; one I like is a simple little late 1980s shooter called Light-Z which 7-zip compresses down to 174k.
I’ve decided to put that 32k tiny Pac-Man style game on the next version of my Desert Island Disc. I would like to have precisely seven games; I haven’t decided whether to make the seventh game the 21st century Tempest clone or the simple shoot-em-up Light-Z.