When I bought my Handspring Treo 600 one of the motivations was the ability download software. I was particularly looking for free (because you don't want to pay for anything you don't have to) versions of Freecell.
First I tried Acid Freecell from Red Mercury. This is absolutely excellent. Good looking, fast running with plenty of options and a good sense of humour employed when putting it together. The game is download-able on a 14 day free trial (although this does automatically extend for a couple of extra days) and costs $14.95 to register.
Second I tried Freecell Solitaire from Electron Hut . Again, a very good implementation of the game. Not quite as good looking as Acid and it doesn't have as many options. It also doesn't throw in the success graphics or humorous lines. Again, you can download a 14 day trial and it costs $11.95 to register.
I'm still running the free trial from Electron Hut so I've yet to try Freecell from freecell.com. Their online version seems quite good (and has a version that looks like a spreadsheet in case you're playing at work). I'll let you know once I've tried it.
If you want a patience collection that is completely free and includes Freecell, try http://www.freewarepalm.com/games/patience.shtml.