Firstly, let me suggest that there is a significant difference between a PDA and a Handheld Personal Computer (HPC).
The concept of a PDA, as coined by John Sculley and created by Apple with the Newton MessagePad, has some fairly basic properties that distinguish it from desktop computers.
Baring these limitations in mind, what can a PDA usefully do?
Since owning a Newton, I have found that I use in three basic scenarios:
Part of the problem here is that I don't use anything similar under Unix already - basically because it is useless to me when I normally need this sort of information. I do have a list of email aliases however, and there is a company phone database.
On the other hand, tables are mandatory and frames are becoming more useful (although not necessary yet).
It's my belief that the best approach is to run a slave daemon on a desktop system which handles the fetching and does some transformation of the info before passing a pre-parsed structure down to the PDA. Using this approach, we can transform all images to a single supported format; grab the first image from a animation; strip font, text colour, background images and so forth before handing it over to the PDA for rendering.
With the support for file:/ URLs, the other vital information access need is also met: local filesystems.
The system must support standard cut and paste to the Newton notepad, and other applications. It'd be cute if there was some format translation done too (so you could retain the HTML) but ...
One of the most useful features of the Newton is the Notepad's ability to store mixed text and images. However, once done, there is no useful way of handling these objects on a desktop machine.
The only widely used format that is vaguely capable of handling such mixed media objects is a web page. With appropriate use of tables and images, the contents of a Notepad page could be rendered into HTML. While there is still no good editor for these pages on Unix, at least it's viewable ...
Of course, it would then be necessary to support a reverse translation, from HTML to Notepad. This is of course useful in itself, and ties in with the cut and paste formating for the web browser.