Python 2.3, or 2.2 if you can live without the many modules that were added (e.g. datetime, csv, logging, optparse, zipimport), aren't using SSL, and are willing to add boilerplate for True/False.
2.4 added decorators. generator expressions, reversed(), sorted(), and the subprocess and decimal modules. Although these are all nice, it's easy to write Pythonic code without them (assuming that your project wouldn't make heavy use of them).
2.5 added with, relative imports, better 64 bit support, and quite a bit of speed. You could live without all of those easily enough.
2.6 isn't released (although it's very close), so while it might appeal to developers, it doesn't have the compatibility you're after.
Take a look at the release notes for 2.3, 2.4, 2.5, and the upcoming 2.6 (use http://www.python.org/download/releases/2.Y/highlights/ where 'Y' is the minor version).
FWIW, for SpamBayes we support 2.2 and above (2.2 requires installing the email package separately). This isn't overly taxing, but the 2.3 additions are useful enough and 2.3 old enough that we'll probably drop 2.2 before long.