System utilities:

Filez for managing what files are on the palm

Applications:

Mapopolis for maps
Calcul-8 to replace the bulit-in calculator
Converter to do conversions

Games:

Blocks, a free Tetris clone
Connect 4
DopeWars
Froggy (Frogger clone)
Galax
MineHunt (Minesweeper clone)
PocketChess
Pyramid (card game)
Sokoban (Web Sailor version: http://www.ngai.f2s.com)
Space Trader (if you like Dopewars, you'll like this. It's like TradeWars on the old dial-up BBS's)
Traffic (mind game)
Vexed (same)

These can all be found at http://www.pilotgear.com/