Personally, I use ATMEGA8-16, which sell for around $1.50 shipped- and has all the resources of the 328 except less flash. I'm soon going to be picking up a 644 to play with and a couple of tiny's, but for the first step off the "standard" 328, I would recommend that you go within the same line so as to get used to flashing a bootloader (or not), getting the right config files, etc isn't quite so "new".
You can always use SoftSerial and define a UART...