First of all, in the example you gave can be implemented with 3 programs:
program 1: 3 minutes, stations 1, 5
program 2: 6 minutes, stations 2, 4
program 3: 9 minutes, stations 3, 6
this is logically easier (and matches what I mean by consolidating the stations according to equal water time), but if you want to optimize, you can implemented it with just 2 programs:
program 1: 6 minutes, stations 2, 3, 4, 6
program 2: 3 minutes, stations 1, 3, 5, 6
As I said, in most case the water time can be consolidated into a small number of groups. The more stations you have, the more likely you can consolidate. I know this is different from other sprinkler timers, but there are cases where you can argue this programming pattern is easier to set and modify than having to set one water time for each individual station.
The storage size is actually more than you thought: the start / end time and interval time each take 2 bytes (granularity of minutes), and water time takes 2 bytes (granularity of seconds). OpenSprinkler 2 supports up to 48 stations, so including the other necessary bytes each program would take a total of 105 bytes. This is quite a bit more than what the current program data structure takes, which is 17 bytes per program.
That being said, Samer and I have talked about how to have a front end that can handle different water time per program, and back end to compress it to more efficient storage. So I will think about this option.