OS: As standard as possible, which basically means "put desktop Linux on it" It's always annoying with these mobile platforms for things to have to be modified to run, or to not have access to standard libs (or missing GPSD). Angstrom is pretty perfect in this respect; Android really doesn't seem open enough to me.

Screen: I'm finding 5 inches at 800x480 to be very nice; higher resolution is obviously better, assuming there's some decent scaling options/dpi-dependent sizing. Transflective is great; even if it looks horrible in sunlight, you can read it.

Software: I want the same programs I run on the desktop (for the most part). Mostly to simplify copying settings around. In terms of generics: web browser, music player, e-mail client, and full terminal (esp. SSH client/server). Root access is definitely a must.

Hardware: I used to think a keyboard was a must, but now not so much. Maybe 4-6 hardware buttons minimum, up to a full keyboard. Pocketable is a must.

-Cameras: One on the back to act as a camera is nice, front-facing seems useless.

-USB host is SO nice to have; the Pandora folks got it right with the full-sized port.

-GPS (with GPSD). This is something that I have yet to see somebody get right (though I haven't gotten to test decently on my Archos 5). SirfStar III would be AWESOME!

-Size: The Archos 5 IT (Android) is just about perfect in size, I've found. A bit smaller would be OK, but not bigger.

-It'd be awesome if somebody put a ThinkPad-esque finish on their device instead of the shiny crap everybody seems to use. Or even matte aluminum.

-Perhaps most importantly, mainline Linux support for all hardware, or at least very easy-to-apply-and-update patches. Preferably broken up by function.

Price/manufacturer: If somebody REALLY got everything right (especially DIY upgrade potential), I'd probably go up to ~$500. I'll admit to hating Apple products, but if they got it right and for some reason completely changed their strategy around and made an open device as described above, I'd still probably buy it.