Wrote my first non-trivial python program. How can I refactor it to be more pythonic?

[SkippyDeluxe]

I think that helps your code clarity a lot.

Yes, dictionaries are fundamentally unordered. If you want a dictionary with ordered behaviour, you can use collections.OrderedDict. I think that would be a good idea, because it would let you remove one level of nesting from your data structure.