As I've been using a PalmOS based pda for quite some years now, I've assembled a standard set of programs I use and like. I thought I should put them down for others to share. So, let's get started:

• AcidSolitaire: not free, but nice solitair game
• Agendus: also not free, but really nice PIM suite for replacing the default Palm ones
• BatteryGraph: see how your device gets along with its battery. Nice to review your daily/weekly usage too
• Bejeweled: this [non-free...] game doesn't need an introduction ;)
• Filez: a really good file manager for PalmOS [free!]. They have some other nice tools on their site too
• Keyring for PalmOS: Free password wallet. Uses good encryption for protecting your passwords, and synchronizes with the keyring plugin for JPilot, one of the *nix Palm suites
• McPhling: free fast task switching program. Define hotkeys, swipes etc for bringing up a menu of last used programs, fast switching between programs etc [just download and install, despite the $12 mark, it works fine]
• MetrO: free metro, bus and tram planner for an awful lot of cities. Really nice program
• OnBoardC suite: Free C-language development environment that runs on and builds code for, the Palm handheld platform
• PalmWijzer: Dutch railways planner. Not free, but worth its money when you travel by train and Interliner a lot
• Plucker offline document viewer: grab websites, documentation, ebooks etc for viewing comforably at your Palm. Free and really nice program
• Progect: project tasks planner
• Pocket Tunes: if your pda doesn't have a build-in mediaplayer, this [non-free] one might be something you're looking for. However, take a look at TCPMP too!
• Quick News: not free, but nice RSS feed reader for you Palm
• SP-103PC: a free scientific calculator
• skinUI: free skinning program for your Palm. There are some nice skins in their repository [along some less nice ones ;)]. Turn of the splash screen for faster theme switching. Also quite a lot of other nice stuff on their site
• snapCalc: a free pop-up calculator for doing quick maths in other applications
• Snapper mail: advanced email program. Do everything you can also do with your desktop counterpart. Too bad it's not free
• Sol Free: free solitaire game. Download the free version from their site, it's good
• Speedy: a free benchmarking program
• TCPMP: The Core Pocket Media Player, a really good, free media player. For the [less legal, because Apple doesn't want it to be used] AAC decoder, check here and here
• Verichat: a non-free Instant Messaging client

Some interesting addresses:

• Freeware Palm software
• Palm Powerups [collection of free tools and tweaks for your Palm device]
• TamsPalm PalmOS weblog
• Treo 650: Missing software
• My Palm bluetooth and Linux HOWTO

Note that I'm not endorsed by any of the above software manufacturers/sites. I just happen to like them