Хранение строк в PROGMEM не отражается на скорости работы Serial. Гораздо больше сказывается скорость самого порта. Вот для примера время вывода строки "01234567890123456789" в порт:
9600 бод
1) SRAM Serial.print() time is 21164.36 us
2) PROGMEM serialprintPGM() time is 21832.36 us
115200 бод
1) SRAM Serial.print() time is 1730.04 us
2) PROGMEM serialprintPGM() time is 1777.04 us
1000000 бод
1) SRAM Serial.print() time is 215.24 us
2) PROGMEM serialprintPGM() time is 210.44 us
У вас в скетче везде 9600, может быть это одна из причин?
Добавлено через 9мин.:На больших скоростях, кстати, из флешки еще и быстрее писать в порт:
2000000 бод
Testing SRAM vs PROGMEM speed form COM:
1) SRAM Serial.print() time is 136.04 us
2) PROGMEM serialprintPGM() time is 107.76 us
Done