Color isn't necessary, but it's nice to have (it tends to use up batteries faster, though). High res screens make text look a little sharper. Most of the moderate/high end PDAs have 320x240 screens, which are fine for most things. Lots of RAM is always good. 8 megs is usually ok, but 16 is available on a lot of units, and it's nice having the extra space. You can also try JackSprat and JackFlash, which are programs that delete and add programs to the ROM to free up the RAM (be careful using them, though). Removable storage devices, like Sony's memory stick, are really helpful. I have a 32 meg stick, and put just about all my files on it. It slows down the PDA a bit, though, since it has to open the files from the stick, which is slower than opening it from RAM.
I use TinySheet4, too, but on my high res screen (320x320) the text is pretty small. You can't zoom the display with TinySheet, so I'm trying Sheet to Go for a while (came with my unit) while I look at other spreadsheet programs. TinySheet is a more powerful program, though.
There's also WordSmith for a word processor (vs. Word to Go, which came with my PDA). For ebooks, I use iSilo (which can read txt files without converting to palm format). CRS is a nice launcher, if you want to get one.
You can also go to Circuit City and play with different PDAs to see which you like.