I did some checking and it looks like the gain is Rc / re WITH the bypass capacitor and
Rc / (re + Re) WITHOUT the bypass capacitor.
Yes, that is right.
Without the bypass capacitor, the gain depends mainly on the ratio of RC/RE if rb is small enough to be negligible.
eg if RC= 50 K and RE= 10 K and rb =150 ohms, gain = 50 / 10.15 = 4.926
Without considering rb, gain = 50 / 10 = 5... very close to the same gain and it doesn't depend on the transistor gain provided the gain is 50 or more.
Incidentally the bypass capacitor should have a low enough reactance so that it is negligible compared to the emitter resistor's resistance at the lowest frequency to be amplified. Otherwise, the gain will drop back to the above situation.
Is it reasonable to say that the transistor amplifier has non-linear frequency dependence?
Yes, it is reasonable. All amplifiers have limited bandwidth, meaning their gain cannot be equal at all frequencies.