The assumptions:
- "photons always travel at the speed of light"
- "photons (in air) have an energy given be E=hf"
- "of water in their path ... same speed, same frequency"
The conclusion:
"This would require their wavelengths in both mediums to be the same,which is not feasible."
"So where is the discrepancy?"
Admittedly, your reasoning doesn't seem incoherent, not inconsistent, because of the premise the argument seems to be based on seems correct: photons "always travel at the speed of light". From this, as speed/velocity is defined by frequency times wavelength, this "leaves us with" wavelength being the same in the water.
"Is my initial assumption incorrect?"
I don't think it is fair to only point out that: yes, it is incorrect - because photons are known for their slowing down in denser materials, and it is the very change, shortening of wavelength, that is a commonly accepted conclusion from the formula above.
There is more depth to your question, in my opinion, because we learn about, in fact, what you say: photons do not even exist if they do not travel, and they mean travel at the speed of light.
It cannot be some blunt pleonasm, like: Its a photon, hence, it always travels at its own speed, because it is light. The statement "photons always travel at the speed of light" refers to the rest mass zero issue - photons are said not to exist if at rest, if not travelling.
In my opinion, the discrepancy lies within the premise. Photons are known not to exist unless travelling, "at the speed of light" - on the other hand, they are known to slow down in denser media.
There are two ways to solve the discrepancy:
Photons "take a break" by interacting with electrons on their way, and this pausing causes their slowing down in media, changing the wavelength, not the frequency (interestingly, the formula on energy you mentioned comes in: does wavelength, not frequency, decide on energy, inside media - in my opinion, that's an argument against the time lag explanation). This pausing would logically be consistent with the idiom "always at the speed of light" if "speed were restricted to the travel, excluding the pausing caused by interaction with electrons (cp. Feynman lectures, Feynman diagrams).
The alternative way to logically reconcile a different wavelength, avoiding a time lag, is to acknowledge refraction within the medium, not at the borders only, that causes a zigzag course of photons thus extending the length of their path, consistent with the saying "photons always travel at the speed of light" - in media, their path is longer, which is caused by refraction. Beware, the velocity of light in media is measured along a straight line from entry to exit, applying the "wavefront" concept.
There are accepted quantum theories that are consistent with assuming a "no time" interaction with electrons, just as it's accepted that any mirroring or refraction (at boundaries of media) do not lead to lagging in time.
Accepting explanation b., you may say
a. Photons "always travel at the speed of light"
b. The wavelength of the wavefront of photons changes in different media because of their zigzagging that extends the distance traveled.