I can get a Pocket PC for $30 on ebay
cool. do it.
you will need one with some sort of port to connect to your robot.
like you say, a USB host port would be most likely on these devices i think.
i know some of these devices will have a USB host port as i have seen little foldable keyboards and other peripherals for them.
probably the easiest way of controlling things from a USB port is with a USB to serial converter connected to a microcontroller's UART.
the other thing you will need is some sort of programming language.
i presume there is a GCC port for embedded windows devices.
if it was me i'd get a linux compatible PDA but maybe you want to stick with the existing OS?
linux would certainly give you far more flexibility but there would be a learning curve if you are not familiar with that operating system all ready.