How can I tell cron to run a command every other day (odd/even)

The syntax you tried is actually ambiguous. Depending on how many days are in the month, some months it will run on odd days and some on even. This is because the way it is calculated takes the total number of possibilities and divides them up. You can override this strage-ish behavior by manually specifying the day range and using either an odd or even number of days. Since even day scripts would never run on the 31st day of longer months, you don't lose anything using 30 days as the base for even-days, and by specifying specifically to divide it up as if there were 31 days you can force odd-day execution.

The syntax would look like this:

# Will only run on odd days:
0 0 1-31/2 * * command

# Will only run on even days:
0 0 2-30/2 * * command

Your concern about months not having the same number of days is not important here because no months have MORE days than this, and for poor February, the date range just won't ever match the last day or two, but it will do no harm having it listed.

The only 'gotcha' for this approach is that if you are on an odd day cycle, following months with 31 days your command will also run on the first of the month. Likewise if you are forcing an even cycle, each leap year will cause one three-day cycle at the end of February. You cannot really get around the fact that any regular pattern of "every other day" is not always going to fall on even or odd days in every month and any way you force this you will either have an extra run or be missing a run between months with mismatched day counts.

I think a possibility is using the day of the year, such like this:

# for odd days
test $(((`date +%j` % 2))) != 0 && command

# for even days
test $(((`date +%j` % 2))) == 0 && command

It is tested for Unix and Linux systems.