Electronic – What do PA and PU mean in AVR lingo

I'd call 16 MHz high frequency, in terms of setting the AVR fuses. Details are in the data sheet, in the System Clock and Clock Options section. Note the startup time options, you shouldn't use 6 CK for a 16 MHz clock.

Your last question is meaningless. The processor speed is determined by the oscillator frequency, up to the maximum frequency specified (16 MHz).

Digikey has excellent selection tools for its components. You can select on package, manufacturer, ADC, and other features. (Odd that memory size doen't seem to be important.)

I found 143 parts matching your requirements. The ATmega48P is 1.76 dollar in 1s and has 4 kB of Flash. The ATmega88P and ATmega168P are the same, but with 8 kB and 16 kB Flash, resp (same datasheet).