If we want to offer customers an option to expedite a bill payment would it be sufficient to disclose these fees at the time the expedite option is selected?

Yes.

Does it matter that the rest of the Reg E disclosure is provided at the time they sign up for the service?

No. They can either accept it at the time of transaction or not do it.

That would seem practical but since reg E requires disclosure of the fees related to the EFT service I was not sure if we had to do a change in terms first.