My DM has some evil dice. These dice seem to roll a much higher than average number of 20s, resulting in a much higher than average critical hit rate against the party. What are some ways a character can protect themselves vs critical hits? My party's current average level is 6, but solutions at any level from 1-20 are welcome. I'm already aware of the fortification magic item properties.
Answers, in order from mechanically-cheapest to mechanically-priciest:
The easiest way is to be a Necropolitan from Libris Mortis: you lose a level as if you’d been killed and had raise dead cast on you, and then lose 1,000 XP on top of that. There’s also some gold involved. In exchange, you become Undead, but lose nothing but your Constitution score.
You are now immune to an enormous smorgasbord of things, and if you dumped Constitution to begin with, you now have effectively a better Point Buy than others. Be careful about your Fortitude save and about Turn/Rebuke Undead – those are weak points for you.
The easiest way to get the Construct type is by being a Warforged (Eberron Campaign Setting), but they have the Living Construct subtype which removes immunity to critical hits. They can fix that, however, by taking the Warforged Juggernaut prestige class from the same book, or by having construct essence from Races of Eberron cast on them (construct essence is a 5th-level Artificer infusion and a 5th-level Sor/Wiz spell; there is also a greater construct essence as a Sor/Wiz 9 spell).
Some other types (e.g. Elemental, Ooze, Plant) and subtypes (e.g. Swarm) also provide immunity to critical hits. These are not nearly as easy to come by as Construct or Undead however; I mention them more for completeness’s sake than as a serious recommendation.
These are effects that give you a % chance to ignore a critical hit (or Sneak Attack). Light fortification is a +1-equivalent for a 25% chance to ignore them, moderate fortification gets 75% for a +3-equivalent, and heavy fortification gets 100% (i.e. immunity) for a +5-equivalent. Ideally, you get a +1 heavy fortification buckler or something, for the minimum 36,000 gp.
Note that all Warforged, not just Juggernauts, get Light Fortification.
The Miniatures Handbook has the 2nd-level cleric spell living undeath, which renders the target immune to critical hits and sneak attacks for 1 minute per caster level. The target suffers a -4 penalty to Charisma for the duration, however, making it a suboptimal choice for sorcerers, most bards and paladins, and some clerics.
Since this question was asked 6 months ago, your party has probably reached level 7 by now, so someone in your party can cast Sandstorm's 4th-level Sor/Wiz spell sandform, which has other benefits in addition to rendering the target immune to critical hits but is much more complex. It also lasts 1 minute per caster level.
Because of their relatively low spell levels both spells can be put into wands, and living undeath can be made into a potion.
Okay, there's something KRyan and Lord_Gareth haven't mentioned yet.
Be a plant. Plants are immune to critical hits, period. Volodni (Unapproachable East), Needlefolk (MM2). Some specific spell also did the job, but I can't remember it, though Polymorph, Polymorph Any Object and Shapechange are fine, too.
Polymorph spells, Iron Body (PHB, 8th level) and Stone Body (PGtF, 6th level) also do the job.
Polymorph Any Object will also do the job.
Well, aside from polymorph spells I can't really remember anything, though there was some specific spell which granted ooze type.
Master of Many Forms gives you Ex special qualities of your new form starting with 7th level and that includes immunities. He can take Plant, Ooze and Elemental forms on 7th, 8th and 9th levels, respectively.
To be continued
If you're a Druid or a Wizard/Sorcerer, the Heart of Air/Earth/Fire/Water spells from Complete Mage will do it. If you have two of them active at once (doable at level 5) you get Light Fortification. If all four are active, you gain crit immunity (not doable until level 9 as Heart of Fire is a 5th level spell).
The nice thing about these spells is that they all have some other effect while they're up, so they're worth casting normally anyway. Heart of Earth for example grants 2*Caster Level temporary hit points. You can also use a swift action to get rid of it, and give yourself a Stoneskin spell temporarily instead (very handy if you suddenly find yourself swarmed!).
Be ready to read a lot of options
Critical hit immunity/protection against critical hits comes in a LOT of flavors in 3.5, which you seem to be playing (since that's the tag on the thread). The easiest method, by far, is to just ditch life and become undead. The Necropolitian template (Libris Mortis) only costs you a level - not a +1 level adjustment, a level, which is easy to gain back - and in exchange gives you the Undead type with its entire suite of immunities and bonuses. Necropolitian doesn't alter your alignment, but talk with your DM about it anyway - as you should for all character options.
Another option is to try and protect yourself from attacks in general. Non-AC defenses such as Mirror Image, Displacement, Blur, Blink, teleportation, flight, and burrowing are great for that, since you can't be struck by a critical hit if you aren't struck in the first place. The Wall of Blades maneuver lets you intercept an attack, and there are some spells and/or class features that can force re-rolls on an enemy.
You might be tempted to go for something like Ysgardian Heartwire (Book of Exalted Deeds) but generally speaking trying to boost your AC is a trap that you shouldn't fall into. Fortification is a pretty good option as far as armor enchantment goes, especially if you can tag it onto an Animated shield (this assumes shield proficiency). Debuffing enemies can help lower their chances of hitting or confirming their criticals - spells like Slow, Blindness/Deafness, Glitterdust, and their ilk prevent an active enemy from hitting/critting effectively.
Some prestige classes grant crit resistance or crit immunity, most notably the Warshaper prestige class from Complete Warrior. If your concept or build permits, Warshaper is a great PrC for melee shapeshifters. A bit of splat-diving can find most of those for you, but the options there are too numerous for me to actually list.