Looking at generalized the generalized requirements (and my budget), I've identified 5 basic approaches, all with wheels:
Although.. perhaps legs are in fact practical. Take a look at RHex, and my ideas for a bug.
A framework within which to evaluate locomotion is to consider some obstacles or paths you want to surmount. In the field, it's mostly random rocks and brush. In an urban or indoor environment, the obstacles are much more structured, which is both a blessing and curse. The blessing is because the obstacles are regularly shaped, often of standarized dimensions or shape, typically at right angles to the direction of travel. The curse is because the obstacles are regularly shaped and standardized dimensions, which means that for some robot configurations, you can get pathologically bad performance, because the robot and obstacle are a "lock and key".
From what I've seen, outdoor random field traversal is accommodated by most designs, assuming you have enough suspension travel (or legs) and large enough wheel diameter. Different designs have different requirements for active control of steering, suspension (pose/body position), and traction, but they're all suitable, some for more or less high speed.
Stairs, on the other hand, particularly ones with no vertical riser or with a lip, can present real problems, particularly for small wheels. And, an even worse problem is stairs at an angle (there's a good reason why you always see photos and videos of robots going straight up and down the stairs), or, a spiral staircase. I set, as a design goal, that the robot should be able to go up and down the stairs in my house. The stair dimensions are fairly normal, 8" (20 cm) rise and 10" (25 cm) tread, carpeted with a 1" (2 cm) lip. But, the stair case turns a corner.
Stairs, Plan view
Stairs, Cross Section
The Mars Rover has a passive suspension system using what's called a rocker bogie. There are 6 wheels, 3 on a side, connected with pivots and a differential gear (so the "body" is always at half the angle between the two sides). The wheels are roughly evenly spaced about twice the wheel diameter apart (at 228 and 254 mm on MPF, with 130 mm wheels). The front and back wheels are steerable. It can go over an obstacle 1.5 times the wheel diameter, which is 30 cm for the 20 cm wheels on the Mars 2003 MER (Mars Exploration Rover). A lot of the JPL design is determined by the need to fit it on a spacecraft, and to be reliably deployed on landing.
http://fido.jpl.nasa.gov/ has information on FIDO, which is sort of a prototype
http://robotics.jpl.nasa.gov/groups/rv/ has pictures of various JPL rovers, most showing Don Bickler's "Rocker Bogie" suspension
This design from Switzerland (http://www.bluebotics.com/ is the commercial outlet) arranges the wheels in a rhombus, that is 1 front wheel, two pairs of middle wheels, then 1 trailing wheel. The two middle wheels on each side are connected with links, and the front wheel has a 4 link suspension with a spring. There isn't any connection between the two sides ( there is a connection in the JPL rover). Just the front and back wheels steer. The inventors claim obstacle climbing of 2 times the wheel diameter (there are videos showing it). For a given size wheel (assuming everything scales), the SHRIMP is a bit longer than the JPL rover, and the center payload area appears smaller. The SHRIMP inventors point out that the suspension is entirely passive, and doesn't require active intervention to handle the terrain. (this is also true of the JPL rovers, and the NOMAD)
A significant flaw, identified by the Rhex folks, in Shrimp (and in the JPL rovers) is that they don't deal well with stairs that have a lip or no solid riser to push the wheel against. However, this is really only the case if the wheel diameter is smaller than the riser height. If one builds a wheeled rover with wheels with the radius the same as the leg length of Rhex, then this isn't as much an issue.
The Koryu-II or KR-II is a snake like robot developed by Shigeo Hirose. It consists of a series of 6 modules connected together. Each module has a single drive wheel on one side (the sides alternate, so that the thing can stand up). There is a sliding joint between sections to allow the relative heights of the sections to vary. There is also an actuator that sets the angle of the attachments (rotation around the "z" axis), and the wheel is always halfway between. This design was never intended for planetary exploration, but more as a firefighter/rescue worker adjunct, so it is modular, can go up and down stairs, etc. Obstacle surmounting is limited more by the vertical travel of the intersegment link than by the size of the wheel. It DOES require active control of everything.
A summary page about KR-II at Hirose's lab
my implementation comments
NOMAD is a big (725 kg) robot built by Carnegie Mellon Robotics Institute to investigate planetary exploration methods. It made a semiautonomous traverse in the Atacama desert and subsequently was used in Antarctica to search for meteorites. NOMAD uses 4 wheels, all of which steer. The steering angles of the wheels on each side are linked with a clever 4 bar mechanism and a lead screw. Each side has a giant rocker bogie, which is linked through a differential to the other side (forcing the body to be halfway between the sides). It can clear an obstacle of half the wheel size, so it has big diameter wheels (76cm diam). Overall, its appearance is reminiscent of the bottom of a "snorkle-lift", which also has 4 wheel steering.