Asus is showing off the P505 Windows smartphone with build-in support VoIP support at Computex 2005. The P505 features a Skype client to offer users Voice over Internet Protocol (VoIP).
So this compact smartphone would prove an ideal solution. The P505 is actually a tri-band GSM handset (so it works in the States). In theory, you might just get away with running Skype over GPRS. However, Wi-Fi would be a more sensible solution and the INQ notes that it is mentioned in the list of compatible accessories. Presumably Asus can supply a SD card style 802.11 interface for the P505.