From a first principles point of view, to move around on a rough surface with a reliable robotic vehicle for extended periods of time, it's probably unavoidable that you need to expend energy. Walking 10km on gravel is more work than a flat surface because the gravel moves and dissipates energy. Walking 10km over rocks that don't move still uses energy because you have to go up and down doing work against gravity and we don't recover that energy.

above: Plot of some randomly selected potentially interesting solar system bodies. Horizontal axis: surface gravity (somewhat related to energy needed to move around) as a ratio to that on Mars. Vertical axis: Approximate sunlight intensity as a ratio to that on Mars - as estimated by ratios of semi-major axis to the -2 power. Venus is listed twice - at the top of the atmosphere where aircraft such as robot balloons and robot planes can collect substantial amounts of light, and the surface where only a few percent of the redder parts of sunlight reach.

above: Page 6 from Venus Aircraft - design evolution 2000-2008, Geoffrey A. Landis, NASA John Glenn Research Center. Above 50km, there is more sunlight available than there is on earth - closer to the sun, and possibility to collect reflected light from below (as does the ISS around Earth) to make up for some cloud cover.

above: Page 32 from Venus Aircraft - design evolution 2000-2008, Geoffrey A. Landis, NASA John Glenn Research Center. The very dense atmosphere makes powered flight very attractive (ballooning as well). However, flying as fast as the wind would be energetically challenging at most altitudes.
Robotic Areal Vehicles may be possible future missions for Venus' atmosphere. It's a long reach, but things taking inspiration from the Festo Air Penguin discussed at length in this answer and shown below, and the Festo Air Ray (not shown) might be possible.
above: Festo Air Penguin discussed more here.
above: Festo Robot Balloon delivering a bottle of water on demand. This would be much more difficult on Venus for a number of reasons, but the higher atmospheric density means balloons could carry a significantly heavier payload, and it wouldn't be necessary to use Helium for buoyancy.
above: Festo Bionicopter could take advantage of the denser atmosphere on Venus. It could also make use of some legs as well!
More about the Vega program using robot balloons on Venus in Wikipedia, in Wired, and in The New Scientist, and future possibilities with NASA's Venus Exploration Group (VEXAG) and ESA's European Venus Explorer (EVE).
Wheels have served humans well over thousands of years. Through zillions of km of trial and error as well as amazing engineering, they’ve solved mobility problems for humans here on earth and on several other solar system bodies.
By far the largest body of detailed experience, imagery and metrology of wheel performance on off-world robotic vehicles comes from the three rovers on Mars.

above: Comparison of Mars Rover Wheels. Left: Sojourner of Mars Pathfinder mission. Center: Mars Exploration Rovers (MER) (Spirit and Opportunity). Right: Curiosity of the Mars Science Laboratory (MSL).

above: Curiosity Self Portrait at Big Sky Drilling Site.

above: Detail cropped from Curiosity Self Portrait at Big Sky Drilling Site.

above: "Location map - Curiosity rover at the base of Mount Sharp - as viewed from Space (MRO; HiRISE; February 4, 2016/Sol 1243)." You have to open this into a separate window and zoom in to see the trail details, starting in the right side of the upper edge. Note that the path is chosen as a compromise between science and where the wheels are judged safe enough to go without getting stuck or damaging the vehicle.
One of the jobs of Curiosity's Mobility System is to cary a large package of Curiosity's Scientific Instruments over large distances so that information can be collected from a wide variety of locations.

above: Curiosity Robotic Arm applying a drill to Martian rock. Samples are then collected and transported to locations inside Curiosity for further analysis using a variety of analytical equipment.

above: Curiosity still ...inside the Spacecraft Assembly Facility at NASA's Jet Propulsion Laboratory, Pasadena, Calif.. Even in Mars's surface gravity only $\frac{3}{8}$ of Earth's, all of this scientific equipment together has gotta be pretty heavy! The robot arm is often forgotten because it doesn't show up in many of Curiosity's selfies in the same way your hand or the business-end of your selfie stick don't show up. But if you look close in the Big Sky Drilling Site "selfie" a few images above - you can see it's shadow on the surface!!
While Boston Dynamics' Big Dog ran on fossil fuel for various reasons (see this Boston Dynamics conference proceeding PDF) including power density and demonstrations for particular non-science "missions", Spot, SpotMini (shown in the question), and LittleDog are electrically powered, and LittleDog seems to be built with off-world use in mind, or at least in the back of the mind.
LittleDog has four legs, each powered by three electric motors. The legs have a large range of motion. The robot is strong enough for climbing and dynamic locomotion gaits. The onboard PC-level computer does sensing, actuator control and communications. LittleDog's sensors measure joint angles, motor currents, body orientation and foot/ground contact. Control programs access the robot through the Boston Dynamics Robot API. Onboard lithium polymer batteries allow for 30 minutes of continuous operation without recharging. Wireless communications and data logging support remote operation and data analysis. LittleDog development is funded by the DARPA Information Processing Technology Office.

above: Little Dog cut-away illustration from Boston Dynamics
above: Video of Little Dog climbing over terrain from here.
above: Video of Boston Dynamics' battery-powered Spot climbing over terrain and getting along well with "Hockey Stick Guy" (here with commentary on YouTube and in Wired) despite getting kicked by him.
Presumably, a main robot rover may also cary one or several more highly mobile rovers for sample collection. Much in the same way that Curiosity's robotic arm can collect samples and transport them to the "laboratory" inside Curiosity, mini-rovers may be able climb up on to, as well as down into hard-to-reach places for measurements, imagery, mapping (via telemetry or data transfer upon return) as well as some kinds of sample collection. While drilling requires force and Curiosity uses mass and leverage, a clever robot could find leverage between rocks or walls, possibly even moving rocks around to improve the situation.
These guys look like they are ready to go anywhere in the solar system!
above: Boston Dynamic's Sand Flea launching itself all over the place! Now imagine this happening on a low surface gravity body. Suborbital (except in extreme cases like comets or small asteroids) but it is point-A to point-B transportation. Needs robust electronics and sensors to avoid getting a headache, but possibly fine for sample collection and scouting.
Currently it uses stored compressed gas for multiple jumps (see below). Some interesting ideas could be imagined to make the gas rechargeable from an atmosphere, or replaced with an electromagnetic linear motor (tiny captive rail-gun-like thing).
The following is from the Sand Flea Datasheet (remember, the specs are for Earth surface gravity!):
SandFlea is a small robot with remarkable mobility. The 11 lb robot drives like a traditional wheeled vehicle on mild terrain, but jumps up to 8m high over difficult terrain. It can jump 25 times using the piston actuator and onboard fuel supply. Jumps of 1-8 m heights are user selectable. Specially designed wheels cushion the shock of landing. Flight and landing attitude of the robot are automatically controlled by an onboard stability system.
- Controllable hop height, 1-8 m
- Controllable launch angle
- Precision hops through windows or doors, on to tables, up staircases, on to or off of roofs or balconies
- Piston actuator
- Laser-based ranging to guide launch
- Operator control unit (OCU) with live video feed for remote operation
- Robot and OCU both fit into a small backpack

above: Boston Dynamics says:
The robot uses gyro stabilization to stay level during flight, to provide a clear view from the onboard camera, and to ensure a smooth landing.
above: Boston Dynamic's RHex going all over the place - looking for water perhaps?
However, they would either need tiny RTGs of their own, solar panels of their own, or have to be charged and then recharged by the main robot. This can be done by contact, or through highly resonant inductive charging - which can actually cover a significant gap of a few meters in a pinch - or just optical charging - laser to special photovoltaics like this:
above: quadcopter illustrative example of a small vehicle receiving power from a beam of light. Note: an aperture of 5 centimeters can "beam" power over many kilometers if atmospheric effects are minimal and motion is minimal.