the smallest AVR with a UART is the S2313 and all bigger ones have at least one UART. All AVRs can be programmed very easy. A programming adapter and the SW you can find at www.lancos.com (ponyprog).
Can you specify your requirements a little bit more?
How much Flash,E²ROM,RAM,speed do you need.
For an USB interface you can use a FT232BM from FTDI. The chip can be conneted to the UART of the AVR.
I thint that an ATmega with Bootloader is a very good option. To program the ATmega for the first time you will need another programmer. As revolt, I suggest you ponyprog and a STK200 or STK300 that you can find at www.lancos.com