Does it do what you want it to do?
Printing. Can you print directly to a printer? Or do you have to return to your desktop PC?
Speed. Is it fast enough? How long does it take to add a contact, or an appointment? If you end up watching an hourglass, the machine is too slow.
Keyboard. How large is it? How responsive? Does the handheld even have one, or is it a bulky extra? Handwriting recognition is only OK for quick notes.
Standard software. Is the built-in software sophisticated enough?
Is it aimed at 'personal information management' (a PIM / organiser)? Or does it have the breadth of a true palmtop computer? Which set of features do you need?
Is there a real word processor? With a spell checker, style sheets, fonts, etc.? Not just a version of Windows Notepad?
Is the diary software flexible? Can it repeat appointments automatically? Can you view your appointments the way you want to, not the way the machine wants to display them?
Is there a built-in spreadsheet? For graphing, and calculations they're invaluable.
Add-on software. How many titles are available? Do they cover your areas of interest?
Are they essential purchases (because the built-in software is limited)? Or are they genuine optional applications?