I've basically implemented the dumbest obstacle avoidance algorithm I could think of:

The code for this is

void
loop()
{
    // If an object is detected, start avoiding by choosing whether
    // to go left or right. Keep turning until the front sensor
    // reports that it is clear of obstacles, then resume driving.
    if (distance[DistanceFront] < ClearanceDistance) {
        // Hard stop, backup, and make sure we turn quickly.
        Drive::Stop();
        delay(500);

        Drive::SetSpeed(2 * Drive::DefaultSpeed);
        Drive::Backward();
        delay(250);

        Drive::Stop();
        Drive::SetSpeed(2 * Drive::DefaultSpeed);

        if (Serial) Serial << "AVOID" << endl;
        if (distance[DistanceLeft] < distance[DistanceRight]) {
            Serial << "turn right" << endl;
            Drive::TurnRight();
        }
        else {
            Serial << "turn left" << endl;
            Drive::TurnLeft();
        }

        // The turning delay needs to make sure to relinquish
        // control so that the sensors continue to update.
        while (distance[DistanceFront] < 2 * ClearanceDistance) {
            Serial << "turning" << endl;
            yield();
        }

        Drive::SetSpeed(Drive::DefaultSpeed);
        Drive::Forward();
    }
    yield();
}

Let's talk about what's going on here.

First, if the sensors don't detect an obstacle, we don't change whatever it is we're doing - we just yield so the other thread can keep running.

If an obstacle is detected (e.g. the front sensor has a reading of less than ClearanceDistance, which is currently 15 cm), the robot stops, backs up for a quarter second, then turns in whichever direction has the most room. It keeps turning until it sees more clear space (twice ClearanceDistance to try to avoid having to turn shortly afterwards), then it drives forward.

Here's the problems that you'll see in the video:

1. The robot doesn't stop immediately - there's momentum and braking that needs to be done.
2. The ultrasonic sensor doesn't do well at angles, with cloth or other soft objects that might absorb sound, and it has a narrow view in front of it.
3. The robot gets stopped but keeps spinning its wheels.
4. The robot gets stopped and it can't turn the wheels - this increases the load and will kill the batteries a lot faster, not to mention causing voltage fluctuations that can kill electronics.
5. The robot wheels will move at different speeds due to terrain, which means it doesn't drive straight.

These problems do have solutions.

1. Pushing the clearance distance out further gives more time to maneuver. Ideally, the robot wouldn't even need to stop in order to avoid obstacles.
2. Multiple kinds of sensors should be used; I'm eyeing infrared sensors like the class Sharp sensors. Another option is a servo-mounted sensor capable of panning and scanning. The different angles might provide different insights.
3. I think this could be solved with an IMU: if there's a sudden deceleration and no corresponding acceleration, we have a good idea that the robot has stopped. It should probably back up and turn around.
4. Wheel encoders are the answer to this, I think. It should happen quickly as part of the drive command; if the wheels aren't turning within a few milliseconds, then the robot should consider itself stuck. An interesting problem here is whether to try increasing the speed (in case we're just moving too slowly) or to try backing up. A contact sensor would help here, like a front bumper. If the sensors detect an obstruction and the wheels aren't moving, try backing up. Otherwise, try speeding up. If we get to some threshold speed and there's no movement, then consider the robot immobilized to save the battery and prevent power issues.
5. The IMU would help with this: when the yaw rate changes but we're driving forward, the individual wheel speeds can be trimmed.

There are some code organization things that I think would be useful here, like keeping track of trim values and maybe even putting them in the EEPROM for later.