They're different is probably the best (and possibly most unhelpful) thing to say...
PalmOS was designed specifically for the original Palm Pilot, and it serves that purpose well, namely contacts, calendar, to dos, etc. Those particular apps on the Palm are, IMHO, superior to the ones on the PPC.
The PPC is essentialy scaled down Windows. In other words, it is a general purpose OS squeezed into a PDA. As such, it has support for network connectivity, a proper web browser, databases, etc.
Palm is busily trying to develop a new version of PalmOS that will compete with PocketPC 2002 at that more general purpose end of the market.
At the end of the day, it is going to boil down to "what do you want it for?" If the basic functionality (contacts, calendar, to dos, etc.) is your thing then you won't go wrong with a cheaper Palm. If multimedia, web browsing, sync-ing with corporate databases and email systems, or running a GPS moving map is more what you're after, then go for the PPC.
Oh yes, if a particular piece of third party software takes your fancy, that might dictate the platform choice. For instance, there's a really nice FAA test prep program for the Palm, but not for PPC, which I found useful.
As for Linux, I believe there have been projects to get it onto both Palms and PPCs. Sharp has a Zaurus PDA that runs Linux (they were flogging them at JavaOne last week). Unless you are really interested in hacking around with Linux, I'd say why bother.