Doom, the grandaddy of first-person-shooter games (ancestor of Quake), has been available under the GPL since 1997, and as a result, you can find a version of Doom playable on practically any device with a screen and buttons.
ItPlaysDoom.com is a site devoted to cataloging and reviewing all the different Dooms floating around out there. Fascinating reading:
The Jornada 820! The result? Carnage!
Doom runs faster on the Jornada than it did on my first Pentium PC. So fast, that the LCD screen can't keep up and blurs slightly. It's full-screen action, complete with sound effects, maps, options, WAD files… everything which makes Doom the fantastic game it is.
Internet Archive mirror from 2007
(via Wonderland)