ATtiny85 and ATmega328 talking together at different clock speeds?

I am currently in the planning stages of a project in which I want to have maybe 2 ATtiny85's dedicated to controlling a single thing each and reporting over I2C to an ATmega328 that will be receiving data and displaying it on an LCD. The ATmega328 will also be running a rotary encoder based menu system that will control the ATtiny85's.

Do the ATtiny85's and the ATmega328 need to be running at the same clock speed for this to work?

If so, can I run say, an ATtiny85-20PU at 16MHz using the internal clock and an ATmega328 using a 16MHz crystal and successfully have them talk over I2C?

Sure. You can do that. The only thing that you must to have is both of them use the same speed for I2C.

The internal clock speed does not normally matter, it may limit very fast (MHz) communication. As a rule of thumb, avoid serial communication that exceeds 1/4 of the clock frequency of the slowest device. AFAIR the default I2C frequency is 100kHz, but 400kHz should work as well.

On an I2C bus the master generates the SCL signal, and the slaves use it as is. Some slaves can stretch the clock cycles, to slow down the bus speed if required.