Moving from the uno to programming AVRs. Please recommend

What are the "4-8K variety"?

I've used ATtiny85, ATTiny84, and ATMega328 and always with ArduinoISP. Never had any problems.