I would not get anything with less than 8 mb of memory.  My old PDA has 4MD
and when the palm reader and the data file were downloaded I ran out of space.
 I just purchased a SONY CLIE-S360 with 16 mb of memory, which should hold me
for a while.  An additional memory stick of up to 128 MB can be added.