I recently ran across Bruce Tognazzini's web site Ask Tog. (I'd previously read his book Tog on Interface - recommended.)
One of his articles was Make Your PalmOne a Monster Machine
My list would include:
TextPlus - Suggests words and phrases as you enter letters. This makes entering text on the Palm hugely more efficient. I'd have a hard time living without this now. The ability to add your own words and phrases makes it even better.
Wikipedia for Palm (and other platforms) - I have the 2 gb version on an SD card. It's great traveling to be able to look up information about where you're going. Or to scratch a curiosity itch when you're away from the Internet.
Noah Pro - a dictionary with 122,000 words. Again, great when traveling and away from the Internet. I always hate it when I come across a word that I don't understand, or aren't sure of the exact meaning.
Bonsai - an outliner for Palm and Windows. I use this to keep to-do lists, shopping lists, ideas, packing lists, etc.
Aigo - a Go game for Palm. Considering the limited capabilities of the platform it plays amazingly well. It probably won't be good enough for a real Go player, but for someone who just fools around like me, it's great. This is the only game I play at all, and I don't play it much. I had a chess game on my Palm for a while, but never used it.
I've also been checking out the software Tog recommends in his Make Your Mac a Monster Machine article.
Surprisingly, I couldn't find an RSS feed for his web site. Tog is falling behind the times!