There is a class of devices between phones and netbooks that used to be called "ultra mobile PCs," (UMPC). They are getting harder to find, and many of them feature Atom chipsets that carry the dreaded PowerVR chipsets (GMA500, GMA600 & derivatives). However, you can find ratings and reviews of them on websites like UMPC Portal and Pocketables. Sizes for these devices range from just over cell phone size into the tablet size range.
For Linux,... Ideally, you want something with an X86 compatible processor & a supported graphics chipset. To avoid the PowerVR chipsets, make sure you take note of any Atom processor they are running and look up either the Intel specs, or the Wikipedia specs for that SoC (System on a Chip). However, limited support for these chips is now available (2D only acceleration, 3D by Mesa software only).
You might want to avoid devices that have been end-of-life'd... Here's the UMPC Portal's list of those;
You can get to the regular products page by dropping the endoflife.php part of the above URL.
One promising device, if you can get one refurbished, is the Gigabyte s1080,... But getting Linux running will be a challenge,... Mostly due to the touch screen drivers;
But there are some suggestions;
For telephone, you'll probably need to go with a SIP compatible softphone like ekiga or linphone, or Google Voice (in the USA only).
I have/had the following; The Pepperpad3, Gigabyte M912m, Viliv S5, Dell Inspiron Duo 1090... The Pepperpad I screwed up, and it is now my sole Windows running machine (for flashing firmware, etc.), The Gigabyte M912m still works ok, The Viliv S5 ... I never got working 100% in Linux (currently have 2D graphics, and touchscreen, but no wireless), and the Dell Duo has been the star of the list,... with 95% of it's devices working at least somewhat (but currently running Ubuntu 10.10 due to device incompatibility with later versions).
Getting Linux running on a mobile device is a challenge,... and often involves hacks, kernel patches, work-arounds, and incomplete device support (like; no multi-touch).
An end-of-life device may be able to be made to run... and some are very hackable. In my opinion, the convertible tablet netbooks with true Intel graphics are the best bet. Gigabyte seems like a safe bet,... but you'll need to search for supported chipsets and product availability. Often wireless can be swapped for compatible chipsets, if it's on minipci or micropci cards