One of the ideas I'm toying around with for Ionotatron is flight on Mars. There is not a great deal of information out there on this subject, which makes it a little difficult to research. Nevertheless, some experimentation is going on in this field and recently I've come across a few articles that may shed some light on it.
For example, here is an article which discusses potential designs for flying robots on Mars. The major issues with flight on Mars include the radically different atmosphere compared to Earth and lower gravity. The lower gravity can be a beneficial thing for liftoff and landing, but the density of the atmosphere means using giant propellers for fixed-wing aircraft or even balloons. If you used a balloon, though, you would still need a means of moving in in a particular direction which would involve either small thruster rockets or using usually large propellers.
Another option would be to use an entomopter, which ironically draws its inspiration from insects here on Earth. In one proposed model, two sets of flapping wings would be used, and the device would be less than a foot in length. Here is an animation demonstration what such an object might look like.
On the ground, some other ideas are being explored, such as this "hedgehog" device which could be used to explore Phobos. The spiked robots would roll around on the low-gravity surface and report back to a "mother ship" orbiting overhead.
And if you didn't catch this article, Lego has announced a fan-designed Curiousity Rover model set for the new year.