Have the comparison function passed in as a parameter then, if it's None, then have it maintain the order of insertion?
No. This would contribute to the confusion, not resolve it. If it's called "ordered dictionary", it shouldn't do sorting at all. If it does sorting, it should be called "sorted dictionary", and mandate a comparison function (which might default to cmp).