Smallest Arduino, "femto", for mounting inside vacuums:
http://www.femtoduino.com/Around 3/4" x 1/2"
More integrated USB http://arduino.cc/en/Main/ArduinoBoardADKseems to combine the usb host shield with the processor, just the thing -- just add wifi. Lots of software.
Appears around 2x3"
Arduino Nano and USB host made to plug together just a different shape, thinner but thicker.
Whichever is easiest to attach the WiFi part.
Power supply seems a problem on the ADK, more than Neato's 5v, but the Nano will run right off that.
Carried by familiar Robot Shop besides the usual suspects. The host shield has software. The usb appears to plug right into the nano board. (Wikipedia misleading on power specs, uses internal levels it seems -- must check supplier specs, voltage regulators)