Electronic – Options for a simple over-temperature cut-off

1. More expensive, as you already found out. But it should give you the highest level of reliability: because the watchdog is completely independent of the microcontroller it will still keep running, and reset the microcontroller when the latter is on fire, so to say. See 4)
2. Brian is against it, but there are cheap microcontrollers in a small package, like the PIC10F200 in SOT-23, which you can use as a retriggerable MMV (monostable multivibrator), which the watchdog actually is. If you would consider a 555, a 10F200 is better: no external parts, and more accurate timing (1% accuracy).
3. a 555? Seriously?
4. The internal watchdog will do if the dedicated IC is too expensive. If you're really paranoid you can think of a scenario where some hardware error will lock up the microcontroller and the watchdog with it. I've never known this happen, but I don't know how well you sleep.

Like pjc50 says 6 seconds is a long time. A typical microcontroller will execute tens of millions of instructions in that time, and then a lot can go wrong. Suppose you're controlling some load with PWM, and a low 10 % duty cycle keeps the dissipation low. Microcontroller goes bananas and the output gets stuck at a high level, 100 % duty cycle. The load doesn't like it, and dies. You don't want to wait 6 seconds for that to happen. There should be some part of your code where you pass much more frequenct. A main loop may be as short as 10 ms, then you could set the watchdog's timeout at 100 ms, for instance. If you kick the dog once every 10 ms, then a timeout means that you missed it 10 times! Once, OK, but ten times is disaster, and you have to take action. The load will be switched off after 100 ms instead of 6 seconds, which may be the difference between dead or alive.

So for polarity reversal causing no damage and requiring no fuse replacement you can use pretty much whatever diode you want and put it in series so that "normal" current flow passes through the diode only if properly plugged in. With the current requirements and voltages that you're working at, this shouldn't be an issue. A simple silicon diode should be fine.

For overvoltage you're going to want a circuit more like what Nick Alexeev suggested in the comment. Essentially a zener diode with a PTC or other type of fuse. The Zener should have a value which is less than the maximum input to your regulator.

So basically, if you reverse batt_in+ and batt_in- the first series diode will prevent any current from flowing and protect your circuit. If batt_in is greater than the breakdown voltage of the zener, it will start pulling down a lot of current, and blow the PTC fuse.

The only extra thing you might do, is to guarantee that the startup current doesn't exceed your PTC's current limit, you can place a resistor on "protected V_IN+" or "protected V_IN-" (in series before the regulator and decoupling capacitor) such that:

(BATT_IN+ - V_forward_diode - Resistor*Maximum_expected_load) >= Vmin_regulator

For the desirability of any specific characteristics for the PTC, the diodes, and everything else, it all depends on your application. In general, I tend to wing it unless I have a real reason to crunch the numbers. I'm also a bit too tired (on my way to bed) to really get into how to calculate what these values should be, but if you need this info ask in a comment and I'll post some tips on getting the numbers.

Though, why not just use a polarized connector for the batteries so that you don't have to worry about whether the connector is plugged in backwards? And in what context are you going to overvolt? Think about these questions too when trying to answer a more complicated design choice (a polarized connector is easier than adding an extra diode, and is less likely to lead to extra design considerations).

Hope that helps!