"As you can probably imagine, a program disk for the full cycle of Easter dates would be a wildly impractical thing as well; it would have to have 5,700,000 steps in order to encode the full cycle of Easter dates."

That assumes that you want to encode the program as a single disc encoding the repeating cycle. But surely you could use a series of program discs to perform successive lookups and offsets and reduce it down to several more manageable discs? e.g. you have one disc that encodes the cycle of offsets of the spring equinox by year, then use that to offset the rotation of the wheel that encodes the lunar cycle...