Grab a cheep Handspring Visor or Palm unit. Use it, see if it's what you want, and then you can decide if you want to move into a featureful portable computer like the iPaq handheld.

I started with a Palm III, then a Palm V (Loved it for it's size, still kinda miss it), and now an iPaq 3630 that is used for entertainment and playing around with things like Linux on it. I found using a GSM phone was all I needed to keep phone numbers. (Gotta love the SIM card, 3 different phones now, and never the need to re-enter the numbers).