I can think of two ways of doing this. Both of which tie in with the robot's AI. One is predominantly a mechanical system, the other predominantly a digital one.
If you're willing to 'see' only in a limited spectrum, you can use a tiny, narrow field-of-view, camera, with a collimated filter.
This would only let you in one very specific direction at a time. Think of peeking through a pipe or tube.
The astute world builder might point out that looking through a tube isn't practical.
But you can get around this by having a hi-speed, low-resolution sensor (hundreds/thousands of frames per second). And then waving it about really quickly to scan the environment. Couple this with the AI the robot has, and you have a plausible vision system.
These sensors exist today and, while not really affordable for the home user, they won't break the bank.
For reference, optical sensors can be made very small. A single sensing element (a pixel) in a Canon EOS 7D is 4.3 x 4.3 um. Micrometers. Suppose you choose to have 'eyes' of 100x100 pixels, the eyes are less than 10% of your robot's size.
To point these eyes about, you wouldn't want motors. Piezo actuators would be my first guess.
By and large, cameras need lenses, otherwise they're uselessly out of focus (trivia: pin-hole cameras are the notable exception to this, and the mechanical system I described parallels a pin-hole camera).
But lenses are; large, heavy, fragile, and expensive. Two of those things are entirely unsuitable for a tiny robot.
The workaround to this is; don't use a lens, capture the out-of-focus image... but on a craftily designed sensor of a particular shape. Because the image follows certain mathematical rules (both because of the sensor and because of physics), it's possible to pour mountains of maths and signal processing techniques to reconstruct the original image to a useful degree.
This paper is what gave me the original inspiration. It's very heavy on maths; but you can skip that entirely. The interesting sections are the Abstract as well as sections 1, 3, and 4.