This is a deceptively simple question. Most of the complications come from your interpretation of sustainable. Let me give you a quick summary and explain why it isn't enough:
Fiberglass insulation is the most common these days. It is easy to install. However, it is not healthy to breath, so the installer must wear protection to avoid contact with skin and inhalation. It has higher embodied energy than cellulose (970 MJ/m^3)
Blown Cellulose (dry) insulation is not as common these days since it settles. This causes the top of the wall over time to become not insulated at all. For a diligent home owner, and depending on how the wall was constructed, this can be fixed by periodically adding insulation from the top of the wall. However, this problem is harder to deal with when there is compaction under windows and other places where it is hard to access later. It has lower embodied energy than fiberglass (112 MJ/m^3). This can easily be used in attics where settling isn't much of a concern.
Wet Cellulose (wet) insulation is very similar to blown cellulose except that it is blown in wet so that it binds to whatever it hits and doesn't settle over time. This is fairly standard, but can only be around 4" thick before you have to start embedding some plastic or other support to help hold up the insulation. It is string enough to not sag, but not when spanning large gaps.
Styrofoam insulation is often used under foundations, but also in walls. It is strong and easy to install, but the manufacture still creates many harmful chemicals, to both those manufacturing it and the general air quality.
Rice Hulls can be used in a similar was as blown cellulose and has similar problems. It can settle, though I haven't been able to find anyone saying how much they settle. It is also an agricultural waste product.
Spray Foam is often used to fill in lots of gaps and is great for sealing your walls. A lot of heat is lost through tiny cracks in walls, around windows, etc. Spray foam in these places can be especially helpful. There are many spray foams available, some claiming to be 'green,' which one is most sustainable could be its own question. Most spray foam is toxic enough that there are warnings on the label saying you shouldn't let it touch your skin.
Sawdust was used a long time ago, but has since been replaced by blown cellulose.
Trade Offs
Do you consider small amounts of ozone 'unsustainable?' What are the trade-offs between ozone depletion and embodied energy (styrofoam vs fiberglass)? What are local labor costs? If one insulation takes twice as long to install, perhaps you'd have been better off installing the easy/cheap one, and putting the rest of the money in solar panels, organic food or any number of other places. Extra thick walls to support extra insulation will (depending on your wall construction method) require extra wall material (wider studs in a framed wall). That could also be factored in.
Thermal Mass
Another thing to consider is thermal mass. It is helpful to have things like concrete, earth, brick and water inside (or a part of your inside wall). This is most helpful in places which have large temperature swings. In these places if it is 70 during the day and 20 at night, your thermal mass can hold your house at daytime temperatures all night, without having to turn on the heat (and visa-versa in the summer with cool nights). In places where the swings are less, thermal mass is less important, though still helpful.
Air Tight
Even if you have highly insulated walls, small gaps which let outside air inside and visa-versa can have a huge impact on heating/cooling bills. Some insulation types are better at preventing these kinds of gaps than others.