(This does assume that you actually meant "EEPROM", rather than program memory (which is usually flash.))
If you read the OP carefully, it's clear they mean code storage, as they write
'the smallest internal (EEP)ROM'
and says 'I have seen is the Atmel ATtiny4/5 which is at 512 bytes'
Note the brackets, and the Tiny4 has that much CODE memory.
Flash is Electrically Erasable Programmable Read only memory.
No, FLASH is FLASH, and EEPROM is EEPROM. they are most definitely not the same, even if they superficially seem similar. A key point of the "electrically erasable" feature of EEPROM is that it is single byte erasable. FLASH is always erased in blocks, and as such is not referred to as "electrically erasable" in order to maintain the distinction.
But I think you are right, the OP was probably referring to code memory.
The smallest PIC I've used is 256 instruction words (384 bytes), and it was OTP not FLASH.