I thought I might add my 2 cents... as I have used Papyrus, AgendaOne and PocketInformant.
- Current version of Papyrus is a bit "long in the tooth" but going through a rewrite
- AgendaOne - everything you might want and very easy to use
- PocketInformant - again, everything you might want ... and a bit more. It has a very robust feature set; great graphics; very customizable.
I have both AgendaOne and PocketInformant installed. I am a heavy PIM user and find myself using PocketInformant exclusively.
For me, installation size is a non issue for me as they all install to a storage card.