What JEDEC says...:
no (internal) connection (pin) (NC)
A terminal that has no internal connection and that can be used as a support for external wiring without disturbing the function of the device, provided that the voltage applied to this terminal (by means of the wiring) does not exceed the highest supply voltage rating of the circuit.
NOTE 1 If higher voltages are acceptable, this should be stated.
NOTE 2 The IEC equivalent term is "blank terminal"; nevertheless, the IEC abbreviation is "NC".
NC, NO CONNECTION: A pin to which no internal electrical connection is present or allowed.
Have a look at "Recommendation for NC Pins (Devices: 33912G5, 33911G5 & 33910G5)" from Freescale Semicoductors: https://www.nxp.com/docs/en/application-note/AN3829.pdf
You will quickly notice that (a) this document does not deal with EEPROMs and that (b) not all NC pins are equal. Even on one single device, different NC pins can have different permitted voltages! There is also at least one Freescale device where a group of NC pins is connected internally to each other (but not to an other group of NC pins in the same IC).
Texas Instruments seems to define "NC" as "No connect (DO NOT CONNECT) externally. Failure to leave NC pins open can cause faulty operation.". On Semiconductor seems to think the same.
ST says (for an EEPROM, so this is, in the strict sense, somehow relevant to the original question): "No connect (NC) pins should be tied to VSS.". Also, "No function (NF) pins should be tied to VSS."
Atmel seems to consider NC an "input" pins (even though without a function) and allows the same voltage range as any other (digital) input pin. Pins which should be left floating (unconnected) are marked "DU" ("Don't Use") by Atmel.
At least one manufacturer mentions that a close-by RF source can inject noise into an IC when an NC pin is left floating. In that (quite possibly rare) case, they recommend tying it to DC (GND/Vcc).
Is it safe to assume that IC manufacturers will do the "right thing"?
Nope. While in a few select cases, manufacturers have indeed taken into account that another of their ICs could be used as a drop-on replacement (like a newer/larger *PROM, which is deliberately made pin-compatible with the older part), they usually don't. Like the 28C256, which is not a possible drop-in replacement for the 27C256. Fun!
You are safe with the scenario you describe with the Atmel AT28C256/AT28C64. I am not aware of any mainstream EEPROMs where an NC pin might have an unpleasant effect when connected to a "regular signal" (just don't connect it to an RF noise source). However, it cannot be completely ruled out that some exotic devices have NC pins with internal connections.