This day and age it is often cheaper to get a phone/pda combo than getting them seperately. It is also considerably less pocket clutter to carry around.
Most of these devices include some dictation capabilities which can be augmented by the add in memory cards.
The Treo's are popular. I was stumbling through Amazon and came across a Motorola MPX220 unit that was $50 after all the rebates.
I recommend looking into the phone/pda combo. My preference is a devices that works with a stylus as the mini-keyboard devices cause me to fat finger too many things.