Out of memory, how to reduce this program's size

It appears that the F() macro helps, but many of your strings are duplicated. You might consider an array of strings to avoid the duplication of the string constants.