Again, I'm surprised several of you mentioned games. I've never played anything beyond Minehunt and Othello while waiting for a plane. Mpiva, what great games did you find?
Redshift has some awesome RPGs. They have amazing graphics but since they're old fashioned turn-based RPGs they're great to play in a casual setting such as a waiting room. You can be in the middle of fighting a monster and, when the nurse calls your name, simply turn it off and continue later. There's no worring about dying because you looked up at the wrong moment.
Warfare Incorporated (sorry can't seem to find a working link) was, by far, the best RTS game on the Palm.
Rifle Slugs was a good Worms-like game.
Ricochet was a great brick-out type game.
And, of course, there was
Bejeweled2.