Palm OS, especially in that price range, rather than a Pocket PC. There is a considerable difference in bulk and geekiness as well - I cannot picture ME carrying a Pocket PC (size and heft), but I feel nekid without a palm pilot.
If you can pony up a few more $ I REALLY like the m500 - the size is tiny but the capabilities are great. The low-mid range Sony devices are nice as well, albeit a bit larger. (The top end Sonys are TOO BIG). There is a new Palm out that is a little out of your price range but is really worth a look: Zire 71. OK; it has a camera, but that's laignape - it has SD/MMC slot and the new hi-res color screen. I like my new color T, but it's the res I really like (possible Sony selling point). The main drawback (for me) to the Sony's is the proprietory memory stick. Get something that can connect with the Palm universal connector and that uses SD/MMC memory expansion.
Don't bother with AA batteries - make sure your device uses Li-ion rechargable power cells. The m130 is a good device, as suggested. You will want to spend a little $ on software/hacks after you've had it a month or so. Grafitti is easy to learn but there are alternatives if you really hate it.
HTH