I have a Dell Axim X5(no longer in production as far as I know) My dell has served me well. It was quite cheap compaired to others, but performace matched price. Mine was rated one of the slowest in it's class. Still, if you want to keep the prices down, Dell has some nice PDAs to choose from now. Also, the X5 was one of their first ones, so their newer ones are much better I'd assume.
Now you need to decide what kind of OS you wnat. There's PPC/Windows which tipically is more multimedia based, but it's harder to find software for(especially free) Palm OS is tipcially more simple stuff, but there's TONS of software to choose from.
Memory is a consideration, but nothing major. Most have a good bit of memory to start with, and you can always expand it.(well, with most of them)
I guess we should know your pricerange first then we could help more from there...