Brent: I use a Treo 650, with lots of utility programs. Voice memo's not one of the built-in features, so from http://mytreo.net I found a very simple, _freeware_ memo tool called SoundRec. Not the greatest sound quality, but it's worked well enough to use it to capture.
(P. S. I too am relatively shy in public, but I don't hesitate to record a memo... since I've got the combination phone-and-Palm, I look like I'm making a quick call to someone, except it's really to a near-future me. hehe)