The solar-powered walking robot is entirely within the realm of reality for you to create. You made no claims as to the speed, duration, or other such specs of your robot, and as such there is little basis for derision of your vision. Claims that the robot will be "powerful" are entirely subjective - an ant can lift several times its own weight, does that make it powerful?
The plan for a small model is a good one. I'd even go so far as to suggest the coin-shaped watch batteries over AAs to keep the robot light. The pager motor idea blueroomelectronics suggested is also a good one. I expect that it would be a reasonable (and thrifty!) plan to modify a wind-up walking toy with a pager motor, watch battery, and solor panel.
Little helicopters like these are proof that "power" can come in small packages:
https://www.youtube.com/watch?v=GQez1-DxJOk
That's more power than your walker robot will need, and it's just a matter of how often you want it to be able to perform. A constant, directly solar-powered robot is unlikely, but there's no shame in that. How far has NASA's latest Mars explorer travelled since it landed?
One final note: the modified wind-up robot I mentioned doesn't have any plan for direction control, but how about this idea? You could mount a second pager motor vertically, with a rough sort of cam on the shaft. When the motor spins in one direction, it knocks the cam against a vertical post on the main body of the robot, hence bumping the entire robot slightly in the direction the vertical motor was spinning. When you want to rotate in the opposite direction, just reverse the vertical motor's direction so that the cam hits on the opposite side of the stationary post. No doubt some theorist on this forum will be tempted to tell you that this defies the laws of physics, but if those laws couldn't be defied, there'd be no way to spin in an office chair without your feet touching the ground.